精华内容
下载资源
问答
  • 文件管理系统算法的伪代码实现
    千次阅读
    2014-05-12 22:26:02
    

     LaTeX 科技排版:包含水平三线图式的伪代码算法排版algorithm


    下面这个文档对排版算法至关重要,请多加练习


                 
                   
    http://blog.renren.com/share/66049300/679318404
     
    中文环境下使用
    http://wwv.renren.com/xn.do?ss=10791&rt=1
    http://www.sciencenet.cn/m/user_content.aspx?id=231910
    Latex live 指南
    Latex 符号指南
      Latex 公式指南
    Latex 图像指南
    http://www.latex-project.org/intro.html
    http://latex.yo2.cn/articles/latex-learning0.html
    2008/8/3 Latex 使用心得
    最近学会了使用 Latex ,并且今年的 First Year Report 就是用 Latex 写的,发现了很多也许有用的小技巧,总结一下。

    工具:

    我现在使用的是 CTex ,一个号称支持中文的 Latex ,不过我现在还用不上中文。该软件免费可下载: http://www.ctex.org/HomePage   里面的 WinEdit 确实是很好用的。编译的内核是 MikTex 2.4 ,有一点老,不过基本功能都有了。
    在 linux 上,可以使用 texmaker ,用了用,还是不错的。
    一些使用心得 :

    插入图片。在 Latex 中,图片是以文件的方式嵌入到文档当中,在转换为 pdf 或者 ps 文件的时候才会嵌入到文件中,否则都是单独存在的。插入图片的基本命令:
    \begin{figure}
    \centering
    \includegraphics[width=0.6\textwidth]{file/vcrouter}
    \caption{Internal structure of a VC router}\label{fig:vcrouter}
    \end{figure}
    \begin{figure} 和 \end{figure} 中间是图片的命令。 \centering 之后的所有内容居中。 \includegraphics 插入图片, width=0.6\textwidth 说明图片的宽度为 0.6 倍页宽,文件名是 file/vcrouter ,用 latex 编译自动搜索后缀为 eps 的图像, pdflatex 编译自动搜索后缀为 pdf 的文件。 \caption 说明该图 片的标题, \label 给出一个标签,文中则可以使用 \ref{} 进行连接。插入图片需要加载 \usepackage{graphicx} 。
    插入多幅图片并包含子图的图片:
    \begin{figure}[ht]
    \centering \subfigure[A bundled-data channel]{
        \includegraphics[width=0.30\textwidth]{file/bundleddata}\label{fig:bundleddata}}
    \hspace{0.1\textwidth} \subfigure[The 4-phase bundled-data
    protocol]{
        \includegraphics[width=0.4\textwidth]{file/4phasebundled}\label{fig:4phasebundled}}
    \caption{The 4-phase bundled-data protocol}\label{fig:4pb}
    \end{figure}
    这是一个两个子图水平并列的例子。在 \begin{figure} 后添加 [ht] 说明以水平 table 的形式排布,当然也可以使用 tabular ,不过麻烦一些。使用 \includegraphics 需要加载 \usepackage{subfigure} 。
    公式编辑。其实可以使用公式编辑器。 MathType 5.0 以上,在 perferences 菜单里的 translators 选择 translate to other languages ,然后选择 latex 。之后,用公式编辑器编辑的公司可以直接用选择和复制放到 latex 文件当中。
    如果公式需要加编号,使用 \begin{equation} 和 \end{equation} 就能自动添加编号。不过最好加载 \usepackage{amsmath} 。另外,默认公式是居中的,如果需要改成靠左缩进的方式,在 \documentclass[fleqn] {firstyearreport} 添加这个 fleqn 选择参数。
    参考文献最好使用 bibtex 管理。管理的软件可以使用 Endnote ,不过我用的是 jabref ,一个开源软件,还是很好用的。只要 写上 \bibliography{file/reference} ,这里的 file/reference 说明参考文献是 file /reference.bib 文件,所有的参考文献就可以自动加载。关于参考文献的风格,我使用的 是 \bibliographystyle{alpha} ,以作者的第一字母和年代为标号。但是还有很多其他的方式,可以参考这个网站: http://www.cs.stir.ac.uk/~kjt/software/latex/showbst.html
    图片格式是一个很烦人的问题。最基本的图片格式是 eps ,尽管现在 pdflatex 支持 pdf 和 jpeg,png 等等,但是我还是认为 eps 比较好。 eps 是矢量图,没有图像失真。用 eps 转换成的 pdf 放大多少都没有问题,体积也很小。
    但是,支持 eps 的软件并不多。在 windows 上,我们最习惯的是 Visio 画图,但是 visio 对 eps 基本上没有支持。网上有很多将 visio 的图转化成 eps 的图的方法,但是很多都很麻烦。我现在终于找到了一种比较好的方式。
    首先安装一个 postscript 的虚拟打印机, http://www.adobe.com/support/downloads/detail.jsp?ftpID=1502 。然后用 visio 将图片用 postscript 打成 prn 或者 ps 文件。用 CTex 自带的 GSview 打开该文件(没有也没关系,下一个: http://pages.cs.wisc.edu/~ghost/ ), file 菜单中有一个 ps to eps ,哈哈,自动转换边界,就变成 eps 文件了,而且是矢量的。
    还有一个问题, pdflatex 偏偏是不支持 eps 文件,默认是 pdf 文件。使用 pdflatex 时,如果没有 pdf 文件会报错。有人说使 用 \usepackage{epstopdf} 可以解决该问题, eps 文件会自动在编译时变为 pdf 文件,但是在 windows 上的使用结果很糟 糕, eps 文件没有自动转换边界,按 A4 打印,结果很难看。
    其实加载 \usepackage{epstopdf} ,就是使用 epstopdf 命令转换 eps 文件。但是在 windows 系统中的 epstopdf 命令好像不能自动转换边界,但是 linux 系统上的 epstopdf 是好的。所以我建议使用 linux 系统上的 epstopdf 命令转 化,是会自动转化边界的。
    不过大批的文件一个一个去手动转化还是很麻烦,我就写了一个 makefile 文件,假设所有的 eps 文件都在一个文件夹下,那么 make all 一下,就能自动转化为 pdf 文件。知道我在说什么吧,呵呵。 Makefile 的内容如下:
    clean:
            rm -f *.pdf
    eps_file = $(wildcard *.eps)
    pdf_file = $(eps_file:%.eps=%.pdf)
    $(pdf_file): %.pdf : %.eps
            epstopdf $<
    all: $(pdf_file)
    show:
            echo $(pdf_file)
    伪代码。伪代码有时候还是要用的,对于复杂的算法,直接写伪代码有时候更容易懂。关于伪代码有一个包 algorithms ,需要加 载 \usepackage{algorithm}\usepackage{algorithmic} , 具体用法可以直接看他的帮助,在下载的压缩包中的 doc 目录下。下载路径: http://www.ctan.org/tex-archive/help/Catalogue/entries/algorithms.html   忘了说了,所有 Latex 相关的文件找不到,或者需要最新版,请查询 http://www.ctan.org/tex-archive/help/Catalogue/entries/algorithms.html   .
    伪代码举例
    \usepackage{algorithm}    %format of the algorithm
    \usepackage{algorithmic}  %format of the algorithm

     
    \begin{algorithm}
    \caption{Calculate $y = x^n$}
    \label{alg1}
    \begin{algorithmic}
    \REQUIRE $n \geq 0 \vee x \neq 0$
    \ENSURE $y = x^n$
    \STATE $y \leftarrow 1$
    \IF{$n < 0$}
    \STATE $X \leftarrow 1 / x$
    \STATE $N \leftarrow -n$
    \ELSE
    \STATE $X \leftarrow x$
    \STATE $N \leftarrow n$
    \ENDIF
    \WHILE{$N \neq 0$}
    \IF{$N$ is even}
    \STATE $X \leftarrow X \times X$
    \STATE $N \leftarrow N / 2$
    \ELSE[$N$ is odd]
    \STATE $y \leftarrow y \times X$
    \STATE $N \leftarrow N - 1$
    \ENDIF
    \ENDWHILE
    \end{algorithmic}
    \end{algorithm}
     
    效果

     
     algorithm宏包的文档指导 /Files/Lhw978/algorithms.pdf
     
     

    LaTex:算法排版

    http://www.binghe.org/2010/03/typeset-algorithm-in-latex/


    排版可能需要的包:
        usepackage{algorithm}    %format of the algorithm
        usepackage{algorithmic}  %format of the algorithm
        usepackage{multirow}     %multirow for format of table
        usepackage{amsmath}
        usepackage{xcolor}
        DeclareMathOperator*{argmin}{argmin}                   %argmin或argmax公式的排版
        enewcommand{algorithmicrequire}{ extbf{Input:}}   %Use Input in the format of Algorithm
        enewcommand{algorithmicensure}{ extbf{Output:}} %UseOutput in the format of Algorithm

    排版图片可能需要的包:
        usepackage{graphics}
        usepackage{graphicx}
        usepackage{epsfig}

    算法的排版举例( 例子代码有误)
    \begin{algorithm}[htb] %算法的开始
    caption{ Framework of ensemble learning for our system.} %算法的标题
    label{alg:Framwork} %给算法一个标签,这样方便在文中对算法的引用
    \begin{algorithmic}[1] %这个1 表示每一行都显示数字
    REQUIRE ~~\ %算法的输入参数:Input
    The set of positive samples for current batch, $P_n$;\
    The set of unlabelled samples for current batch, $U_n$;\
    Ensemble of classifiers on former batches, $E_{n-1}$;
    ENSURE ~~\ %算法的输出:Output
    Ensemble of classifiers on the current batch, $E_n$;
    STATE Extracting the set of reliable negative and/or positive samples $T_n$ from $U_n$ with help of $P_n$; label{code:fram:extract} %算法的一个陈述,对应算法的一个步骤或公式之类的; label{ code:fram:extract }对此行的标记,方便在文中引用算法的某个步骤
    STATE Training ensemble of classifiers $E$ on $T_n cup P_n$, with help of data in former batches; label{code:fram:trainbase}
    STATE $E_n=E_{n-1}cup E$; label{code:fram:add}
    STATE Classifying samples in $U_n-T_n$ by $E_n$; label{code:fram:classify}
    STATE Deleting some weak classifiers in $E_n$ so as to keep the capacity of $E_n$; label{code:fram:select}
    RETURN $E_n$; %算法的返回值
    end{algorithmic}
    end{algorithm}
    排版效果图


    在文中对算法和算法的某个步骤的引用:Therefore, in step
    ef{code:fram:extract} of algorithm
    ef{alg:Framwork}, we extract $T_n$, a set of reliable negative samples
    1、 For和While循环语句的排版举例
    (1) 排版效果图


    (2)排版代码( 例子代码有误)
    \begin{algorithm}[h]
    caption{An example for format For & While Loop in Algorithm}
    \begin{algorithmic}[1]
    FOR{each $iin [1,9]$}
    STATE initialize a tree $T_{i}$ with only a leaf (the root);\
    STATE $T=T?igcup T_{i};$\
    ENDFOR

    FORALL {$c$ such that $cin RecentMBatch(E_{n-1})$} label{code:TrainBase:getc}
    STATE $T=T cup PosSample(c)$; label{code:TrainBase:pos}
    ENDFOR;

    FOR{$i=1$; $i<n$; $i++$ }
    STATE $//$ Your source here;
    ENDFOR

    FOR{$i=1$ to $n$}
    STATE $//$ Your source here;
    ENDFOR

    STATE $//$ Reusing recent base classifiers. label{code:recentStart}
    WHILE {$(|E_n| leq L_1 )and( D
    eq phi)$}
    STATE Selecting the most recent classifier $c_i$ from $D$;
    STATE $D=D-c_i$;
    STATE $E_n=E_n+c_i$;
    ENDWHILE label{code:recentEnd}

    end{algorithmic}
    end{algorithm}
     
     
      算法 algorithm 重命名
      http://bbs.ctex.org/viewthread.php?tid=49008
    使用 \usepackage{algorithm2e} 如何 使得 caption {}排版结果产生的“Agorithm”变为 " 算法 "?

    milksea 回复:
    改这两个
    \renewcommand{\listalgorithmcfname}{List of Algorithms}
    \renewcommand{\algorithmcfname}{Algorithm}

    问题解决
     

    ,谢谢


     
     
    附录。需要插入附录的话,下面的命令会很有用
    \appendix
    \appendixpage
    \addappheadtotoc
    \appendix 说明之后的内容为附录, \appendixpage 将添加一个专门的附录页, \addappheadtotoc 将附录添 加到目录当中,需要加载 \usepackage{appendix} 。不过,一旦附录开始,将不能转回正文。另一种方式可以使用 \begin{appendices} 和 \end{appendices} 在正文中添加附录,参看 http://www.tex.ac.uk/cgi-bin/texfaq2html?label=appendix
    关于文档中的引用链接和生成 pdf 的链接目录,只能使用 pdflatex 。方法是加载 \usepackage{hyperref} ,所有链接自动生成。
    关于所有的 latex 相关的命令,有一本手册(书) http://tobi.oetiker.ch/lshort/lshort.pdf ,好像有中文的翻译版本 http://net.ytu.edu.cn/share/%D7%CA%C1%CF/lshort-cn.pdf
    哈哈,还有一个事, space 访问量过万了。 2008 年 8 月 3 日 。
     
     
    源地址: http://www.cnblogs.com/Lhw97 8/admin/javascript:showReg(0);                                           
    更多相关内容
  • PageRank 算法实现

    千次阅读 2021-06-02 10:35:52
    实验二 文档倒排索引算法实现 实验三 PageRank 算法实现 实验目的 倒排索引(Inverted Index)被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射,是目前几乎所有支持全文索引的搜索引擎都...

    大数据管理与分析实验报告

    实验一 大数据系统基本实验

    实验二 文档倒排索引算法实现

    实验三 PageRank 算法实现


    实验目的

    PageRank 网页排名的算法,曾是Google 发家致富的法宝。用于衡量特定网页相对于搜索引擎索引中的其他网页而言的重要程度。通过对PageRank 的编程在Hadoop 和Spark 上的实现,熟练掌握MapReduce 程序与Spark 程序在集群上的提交与执行过程,加深对MapReduce 与Spark 的理解。

    实验平台

    • 操作系统:Ubuntu Kylin
    • Hadoop 版本:2.10.1
    • JDK 版本:1.8
    • Java IDE:Eclipse 3.8

    实验内容

    在本地eclipse 上分别使用MapReduce 和Spark 实现PageRank 算法,Spark程序可采用Java、Python、Scala 等语言进行编程。数据集中每一行内容的格式:网页+\t+该网页链接到的网页的集合(相互之间用英文逗号分开)。例如,下图为其中一行的数据,因为一行显示不出来所以使用多行显示。
    在这里插入图片描述
    要求能够利用PageRank 算法的思想计算出每个网页的PR 值(迭代10 次即可),在伪分布式环境下完成程序的编写和测试。

    实验要求

    实验结果为连续迭代10 次后的输出结果
    两个程序输出的结果格式均为(网页,PR 值),其中PR 值保留10 位小数,
    部分结果如下所示:
    在这里插入图片描述
    标准输出存放在hdfs 上/output/PageRank 目录,使用diff 命令判断自己的输出结果与标准输出的差异

    diff <(hdfs dfs -cat /output/FinalRank/part-r-00000) <(cat /home/hadoop/Desktop/part-r-00000)
    

    实验思路

    PageRank算法不再介绍。
    代码中主要有3个类:GraphBuilder,PageRankIter,PageRankViewer,分别完成构建网页之间的超链接图,迭代计算各个网页的PageRank值,按PageRank值从大到小输出,通过PageRankDriver实现多趟MapReduce的处理。
    代码中有一些注释说明,不算很难,按照课上和PPT思路完成即可。

    实现代码

    package org.apache.hadoop.examples;
    
    import java.io.IOException;
    
    import org.apache.hadoop.conf.Configuration;
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.DoubleWritable;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.io.WritableComparable;
    import org.apache.hadoop.io.WritableComparator;
    import org.apache.hadoop.mapreduce.Job;
    import org.apache.hadoop.mapreduce.Mapper;
    import org.apache.hadoop.mapreduce.Reducer;
    import org.apache.hadoop.mapreduce.lib.input.FileInputFormat;
    import org.apache.hadoop.mapreduce.lib.output.FileOutputFormat;
    
    public class exp3 {
    	
    	// 建立网页之间的超链接图
    	public static class GraphBuilder {
    			
    		public static class GraphBuilderMapper extends Mapper<LongWritable, Text, Text, Text> {
    			
                @Override
    			protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
    			    // map:逐行分析原始数据,输出<URL, (PR_init, link_list)>
                    String pr = "1.0";  // PR值初始化为1.0
                    String[] tmp = value.toString().split("\t");
                    context.write(new Text(tmp[0]), new Text(pr + "\t" + tmp[1]));
    			}
    
            }
    
            public static void main(String[] args) throws Exception {
                Configuration conf = new Configuration();
                Job job = Job.getInstance(conf, "GraphBuilder");
                job.setJarByClass(GraphBuilder.class);
                job.setOutputKeyClass(Text.class);
                job.setOutputValueClass(Text.class);
                job.setMapperClass(GraphBuilderMapper.class);
                FileInputFormat.addInputPath(job, new Path(args[0]));
                FileOutputFormat.setOutputPath(job, new Path(args[1]));
                job.waitForCompletion(true);
            }
    	}
    
    	// 迭代计算各个网页的PageRank值
        public static class PageRankIter {
            
            private static final double d = 0.85;  // damping阻尼系数
    
            public static class PRIterMapper extends Mapper<LongWritable, Text, Text, Text> {
            	
            	@Override
            	protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
            		String[] tmp = value.toString().split("\t");
                    // tmp[0]:当前网页 tmp[1]:pr tmp[2]:指向网页
                    String url = tmp[0];
                    double cur_rank = Double.parseDouble(tmp[1]);
                    if (tmp.length > 2) {
                        String[] link_list = tmp[2].split(",");
                        for (String linkPage : link_list) {
                            context.write(new Text(linkPage), new Text(String.valueOf(cur_rank / link_list.length)));
                        }
                    }
                    context.write(new Text(url), new Text("|" + tmp[2]));  // 做个标记"|"
            	}
            	
            }
            
            public static class PRIterReducer extends Reducer<Text, Text, Text, Text> {
    			
            	@Override
            	protected void reduce(Text key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
            		double new_rank = 0;
                    String url_list = "";
                    for (Text value : values) {
                        String tmp = value.toString();
                        if (tmp.startsWith("|")) {  // 标志着链出信息
                            url_list = tmp.substring(1);
                        } else {
                            new_rank += Double.parseDouble(tmp);
                        }
                    }
                    new_rank = d * new_rank + (1 - d);  // 不是 (1-d)/N
                    context.write(key, new Text(String.valueOf(new_rank)+"\t"+url_list));
            	}
    		}
    
            public static void main(String[] args) throws Exception {
                Configuration conf = new Configuration();
                Job job = Job.getInstance(conf, "PageRankIter");
                job.setJarByClass(PageRankIter.class);
                job.setOutputKeyClass(Text.class);
                job.setOutputValueClass(Text.class);
                job.setMapperClass(PRIterMapper.class);
                job.setReducerClass(PRIterReducer.class);
                FileInputFormat.addInputPath(job, new Path(args[0]));
                FileOutputFormat.setOutputPath(job, new Path(args[1]));
                job.waitForCompletion(true);
            }
        }
        
        // 将PageRank值从大到小输出
        public static class PageRankViewer {
        	
        	public static class PRViewerMapper extends Mapper<LongWritable, Text, DoubleWritable, Text> {
        		
        		@Override
        		protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
        			String[] tmp = value.toString().split("\t");
                    context.write(new DoubleWritable(Double.parseDouble(tmp[1])), new Text(tmp[0]));
        		}
        	}
    
        	public static class DescDoubleComparator extends DoubleWritable.Comparator {
        		
        		public float compare(WritableComparator a, WritableComparable<DoubleWritable> b) {
        			return -super.compare(a, b);
        		}
         
        		public int compare(byte[] b1, int s1, int l1, byte[] b2, int s2, int l2) {
        			return -super.compare(b1, s1, l1, b2, s2, l2);
        		}
        	}
    //        public static class DecDoubleWritable extends DoubleWritable {
    //            
    //            @Override
    //            public int compareTo(DoubleWritable o) {
    //            	return -super.compareTo(o);
    //            }
    //        }
        	
        	public static class PRViewerReducer extends Reducer<DoubleWritable, Text, Text, Text> {
        		
        		@Override
        		protected void reduce(DoubleWritable key, Iterable<Text> values, Context context) throws IOException, InterruptedException {
        			for (Text value : values) {
        				context.write(new Text("(" + value + "," + String.format("%.10f", key.get()) + ")"), null);
                    }
        		}
        	}
    
            public static void main(String[] args) throws Exception {
                Configuration conf = new Configuration();
                Job job = Job.getInstance(conf, "PageRankViewer");
                job.setJarByClass(PageRankViewer.class);
                job.setOutputKeyClass(DoubleWritable.class);
                job.setOutputValueClass(Text.class);
                job.setMapperClass(PRViewerMapper.class);
                job.setSortComparatorClass(DescDoubleComparator.class);
                job.setReducerClass(PRViewerReducer.class);
                FileInputFormat.addInputPath(job, new Path(args[0]));
                FileOutputFormat.setOutputPath(job, new Path(args[1]));
                job.waitForCompletion(true);
            }
        }
        
        public static class PageRankDriver {
        	
        	private static int times = 10;
        	
        	public static void main(String[] args) throws Exception {
    			String[] forGB = {"", args[1] + "/Data0"};  // GraphBuilder
    			forGB[0] = args[0];
    			GraphBuilder.main(forGB);
    			
    			String[] forItr = {"", ""};  // PageRankIter
    			for (int i = 0; i < times; i++) {
    				forItr[0] = args[1] + "/Data" + i;
    				forItr[1] = args[1] + "/Data" + (i + 1);
    				PageRankIter.main(forItr);
    			}
    			
    			String[] forRV = {args[1] + "/Data" + times, args[1] + "/FinalRank"};  // PageRankViewer
    			PageRankViewer.main(forRV);
    		}
        }
        
        // 主函数入口
        public static void main(String[] args) throws Exception {
        	PageRankDriver.main(args);
        }
    }
    

    实验结果

    在这里插入图片描述
    在这里插入图片描述

    反思总结

    其实课上包括PPT已经讲了很多用MapReduce实现PageRank的算法介绍和具体细节,如果对于Java编程和Hadoop的API已经足够了解,那么根据这个思路和伪代码实现应该是不算难的,如果有问题,参考一些其他博客也能实现。
    对我而言,更多接触的是C++和Python,Java编程菜鸟,顶多读懂,写这次实验还是需要不停地查一些资料,一些地方的报错不能理解,比如注释掉的DecDoubleWritable类,用它实现的代码不能得到最后的结果(理论上可以,但菜鸟不会调试Java),换成DescDoubleComparator再设置job.setSortComparatorClass(DescDoubleComparator.class)就能跑出结果。
    Hadoop编写的代码,PageRank迭代时需要从文件读,再写到文件里,所以map和reduce的输入输出类型需要特别注意,最初写代码时就困惑于此,以为reduce的输出应该就是下一轮的输入了,但其实还要经过文件读写。
    另外,Hadoop的API真的是一言难尽,官网上API的介绍也没有那么友好,写代码的时候我就没搞懂job.setOutputKeyClass和job.setOutputValueClass这两个常常用到的函数究竟是指谁的(具体可见这里)。

    展开全文
  • Word利用Aurora插入伪代码

    千次阅读 2021-07-20 16:44:29
    最近论文中要插入伪代码,网上主流的方法都是Aurora,但自己安装的时候遇到各种问题。。。这个古老的插件实在是太麻烦了。 正常安装的话应该是只支持32位的Office(这年头了谁还用32位啊)。 操作系统:Win10 ...

    最近论文中要插入伪代码,网上主流的方法都是Aurora,但自己安装的时候遇到各种问题。。。这个古老的插件实在是太麻烦了。
    正常安装的话应该是只支持32位的Office(这年头了谁还用32位啊)。

    操作系统:Win10
    Office版本:2019, 64位

    需要安装Aurora+MikTex2.9,下载地址

    1 安装

    1. 先安装MiKTeX 2.9
    2. 然后安装Aurora,安装时不要选miktex
    3. 再运行keygen进行破解

    (网上好多教程说把时间改成2009年或2005年,但自己Office改时间后就会出问题,所以自己没这么设置)
    自己都没有安装在默认路径,而是装在了D盘,事实证明不影响使用。

    2 设置

    设置paths,找到自己安装路径中相应文件填入。
    在这里插入图片描述
    这时就可以写一些简单的代码了。比如
    在这里插入图片描述

    3 伪代码配置

    伪代码需要安装额外的包,网上常见的说法是在 Packages 中输入,但自己一直报错说

    problems running latex

    3.1 设置 Rendering method
    在这里插入图片描述
    3.2 【重要】安装包!!!
    自己一开始安装网上教程一直不成功的原因就是这里。
    管理员身份运行 miktex-console.exe ,自己的位置在

    D:\Software\MiKTeX_Aurora\MiKTeX\miktex\bin\x64

    在这里插入图片描述
    3.3 添加包
    这个网上有很多示例了,差别不大。下面摘录几个,备用。
    自己用的是第二个。第一个的包看上去更多一些,但常见的代码用第二个就够用了。
    如果用第一个的话还是会报错 problems running latex,应该是还需要下载别的库,自己就先不折腾了。

    \usepackage{amsmath}
    \usepackage{amssymb}
    % \usepackage{euler}
    \providecommand{\abs}[1]{\left\lvert#1\right\rvert}
    \providecommand{\norm}[1]{\left\lVert#1\right\rVert}
    \usepackage{bbm}
    \usepackage{CJK}
    \usepackage{listings}
    \usepackage{xcolor}
    \usepackage{listings}
    \usepackage{amsmath,bm,graphicx,multirow,bm,bbm,amssymb,psfrag,algorithm,subfigure,color,mdframed,wasysym,subeqnarray,multicol}
    
    \usepackage{algorithm}
    \usepackage{algpseudocode}
    \usepackage{amsmath}
    \renewcommand{\algorithmicrequire}{\textbf{Input:}}
    \renewcommand{\algorithmicensure}{\textbf{Output:}}
    
    
    \documentclass{article}
    
    \usepackage{multirow}
    \usepackage{algorithm}
    \usepackage{algpseudocode}
    \usepackage{amsmath}
    \usepackage{geometry}
    \usepackage{algorithmicx}
    \usepackage{algpseudocode}
    
    \renewcommand{\algorithmicrequire}{\textbf{Input:}} % Use Input in the format of Algorithm
    \renewcommand{\algorithmicensure}{\textbf{Output:}} 
    

    4 编写伪代码

    在这里插入图片描述

    下面提供几个示例
    示例1

    \renewcommand{\thealgorithm}{1}
    \begin{algorithm}[H]
    \caption{algorithm caption} %算法的名字
    \hspace*{0.02in} {\bf Input:} %算法的输入, \hspace*{0.02in}用来控制位置,同时利用 \\ 进行换行
    input parameters A, B, C\\
    \hspace*{0.02in} {\bf Output:} %算法的结果输出
    output result
    \begin{algorithmic}[1]
    \State some description % \State 后写一般语句
    \For{condition} % For 语句,需要和EndFor对应
      \State ...
      \If{condition} % If 语句,需要和EndIf对应
        \State ...
      \Else
        \State ...
      \EndIf
    \EndFor
    \While{condition} % While语句,需要和EndWhile对应
      \State ...
    \EndWhile
    \State \Return result
    \end{algorithmic}
    \end{algorithm}
    

    效果
    在这里插入图片描述
    示例2

    \renewcommand{\thealgorithm}{1}
    \begin{algorithm}[H] 
    \caption{*******************************************} 
    \label{ABCLFRS}
    \begin{algorithmic}[1] 
    \Require{S,$\lambda$,T,k} 
    \Ensure{$\mathbf{w}_{222}$}\\ 
    \textbf{initialize}: Set $\mathbf{w}_1 = 0$ 
    \For{$t = 1,2,...,T$} 
    \State Choose $A_t \subset[m]$
    \EndFor
    \end{algorithmic} 
    
    \end{algorithm}
    
    

    效果
    在这里插入图片描述
    示例3

    \begin{algorithm}[H]  
          \caption{algorithm1}  
          \label{your label}  
          \begin{algorithmic}[1]  
            \Require  
              Enter .....;  
            \Ensure  
              Outpur......  
            \State state1......  
            \State state2......  
            \State state3......  
            \While{(a$>$b)}  
          
                \State  state4......  
                \If { c$<$d}  
                    \State state5......  
                \Else  
                    \State state6......  
                \EndIf  
                \State state7......  
            \EndWhile  
            \For{aaa}  
                \State state8......  
            \EndFor  
          \end{algorithmic}  
        \end{algorithm}
    

    效果
    在这里插入图片描述

    参考

    此次安装中以下文章提供了帮助,感谢作者!
    office中的Aurora公式插件,超好用(含下载安装包)
    Aurora中出现报错Problems running LaTex,已解决
    Aurora problems running latex 的解决
    Word2016写论文之——安装Aurora编辑Latex公式及书写伪代码

    重点感谢下面几篇!
    【latex】2 使用Aurora与在word中编写伪代码
    如何在Word中优雅地插入伪代码
    word2016中写出伪代码
    如何在WPS/WORD中解决Aurora的运行问题

    展开全文
  • 算法伪代码: 2. 解码及计算适应度  将优化目标定义为总加工时间最短,因此适应度定义为最短加工时间的倒数,设fitness为对应个体的适应度,fulfillTime为最短加工时间,因此  其中fulfillTime的...

    作业车间调度问题描述

           作业车间调度(Job shop scheduling problem, JSP) 是车间调度中最常见的调度类型,是最难的组合优化问题之一,应用领域极其广泛,涉及航母调度,机场飞机调度,港口码头货船调度,汽车加工流水线等,因此对其研究具有重大的现实意义。科学有效的生产调度不但可以提高生产加工过程中工人、设备资源的高效利用,还可缩短生产周期,降低生产成本。

    作业车间调度问题描述:

    一个加工系统有M台机器,要求加工N个作业,其中,作业i包含工序数为L_{i}。令,则L为任务集的总工序数。其中,各工序的加工时间已确定,并且每个作业必须按照工序的先后顺序加工。调度的任务是安排所有作业的加工调度排序,约束条件被满足的同时,使性能指标得到优化。作业车间调度需要考虑如下约束:

    1. 每道工序在指定的机器上加工,且必须在前一道工序加工完成后才能开始加工。
    2. 某一时刻1台机器只能加工1个作业。
    3. 每个作业只能在1台机器上加工1次。
    4. 各作业的工序顺序和加工时间已知,不随加工排序的改变而改变。

    问题的数学模型:

          令(i,j)表示作业i的第j个工序。S_{ij}T_{ij}分别表示(i,j)的加工起始时刻和加工时间。Z_{ijk}表示(i,j)是否在第k台机器上加工:如果(i,j)在第k台机器上加工,Z_{ijk} = 1;否则,Z_{ijk} = 0C_{k}为第k台机器的完工时间,则问题的数学模型如下:

         公式(1)为目标函数,即优化目标,系统中使用总加工时间最短为优化目标。公式(2)表示1个作业只能在加工完成前一道工序后才可以加工后一道工序。公式(3)表示1个作业的第1道工序的起始加工时刻大于或等于0。公式(4)表示在1台机床上不会同时加工1个以上的作业。

    遗传算法

           随着遗传算法(genetic algorithm (GA))在组合优化问题的广泛应用,许多人开始对遗传算法进行深度研究。已有研究结果表明,遗传算法对求解作业车间调度问题具有较好的效果,因此系统采用遗传算法来解该问题,遗传算法是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。系统通过模拟生物进化,包括遗传、突变、选择等,来不断地产生新个体,并在算法终止时求得最优个体,即最优解。

    遗传算法解决作业车间调度问题基本步骤

    1. 初始化一定数量的种群(染色体编码)
    2. 计算个体适应度(染色体解码)
    3. 采用锦标赛法选择染色体并交叉产生新个体
    4. 个体(染色体)变异
    5. 达到遗传代数终止算法并从中选取适应度最优的个体作为作业车间调度问题的解

    流程图如下

    遗传算法所需参数

    1. 种群规模:种群中个体的数量,用populationNumber表示
    2. 染色体长度:个体的染色体的长度,用chromosomeSize表示
    3. 交叉概率:控制交叉算子的使用频率,用crossProbability表示,并且值为0.95
    4. 变异概率:控制变异算子的使用频率,用mutationProbability表示,并且值为0.05
    5. 遗传代数:种群的遗传代数,用于控制遗传算法的终止,用times来表示

    遗传算法实现基本步骤及伪代码

    1. 编码及初始化种群

           采用工序实数编码来表示染色体,即M台机器,N个工件,每个工件的工序数为process_{i} (0 <= i < N),则染色体长度为chromosomeSize = \sum process_{i},对染色体编码如下:chromosome = { ..., w_i, w_j, w_k, ... }。其中w_i代表第i个工件编号,而出现的次数代表该工件的第几道工序。例如{0, 1, 2, 1, 2, 0, 0, 1, 2},中0,1,2表示工件的编号,第几次出现就代表第几道工序。然后将每一次随机生成的染色体个体加入到种群集合中。

    算法伪代码:

    2. 解码及计算适应度

           将优化目标定义为总加工时间最短,因此适应度定义为最短加工时间的倒数,设fitness为对应个体的适应度,fulfillTime为最短加工时间,因此                                                       

    其中fulfillTime的计算方法如下:

    首先定义如下变量

    然后从左到右遍历个体的染色体序列{..., w_i, w_j, w_k, ...},其中w_i表示第i个工件的编号,则w_i对应的当前工序为processIds_{w_i},设为p。当前工件当前工序所使用的机器编号为machine_{w_i, p},设为m。当前工件当前工序对应的加工时间为time_{w_i, p},设为t。则工件的第p道工序的最晚开始时间为          

    而第m台机器的加工时间为                                   

    工件w_i的第p道工序的结束时间为

    最后加工完所有工件的最短加工时间fulfillTime为

    从而计算出适应度fitness。

    伪代码如下:

    3. 个体选择算子

    个体的选择使用锦标赛法,其基本策略为从整个种群中随机抽取n个个体让它们竞争,选取其中最优的个体。该算子的选择过程如下

    伪代码如下:

    4. 染色体交叉算子

    使用Order Crossover(OX)交叉算子,该算子的交叉步骤如下:

    对于一对染色体g1, g2,首先随机产生一个起始位置start和终止位置end,并由从g1的染色体序列从start到end的序列中产生一个子代原型

     

     将g2中不包含在child prototype的其余编码加入到child prototype两侧

    上述步骤将产生一个child,交换g1, g2即可产生另一个child

    伪代码如下:

    5. 染色体变异算子

    变异的作用主要是使算法能跳出局部最优解,因此不同的变异方式对算法能否求得全局最优解有很大的影响。使用位置变异法作为变异算子,即从染色体中随机产生两个位置并交换这两个位置的值

    伪代码如下:

    6. 算法整体伪代码如下:

    遗传算法代码实现

    根据上面的步骤及伪代码,很容易就能写出Python及Java对应的代码实现了,如下:

    Python代码:

    from random import (randint)
    from typing import (List, Tuple, Set, Dict, Any)
    from utils.utils import reshape_data
    from collections import namedtuple
    
    MATRIX_SIZE = 500
    
    
    # 个体对象,染色体和适应度
    class Gene(object):
        def __init__(self, fitness: float = 0, chromosome = None):
            self.fitness = fitness
            self.chromosome: list = chromosome
    
        def __eq__(self, other):
            if isinstance(other, Gene):
                return other.fitness == self.fitness and other.chromosome == self.chromosome
            return False
    
        def __hash__(self):
            return hash("".join(map(lambda x: str(x), self.chromosome)))
    
        def __str__(self):
            return "{} => {}".format(self.chromosome, self.fitness)
    
    
    # 存储解码结果
    class GeneEvaluation:
        def __init__(self):
            self.fulfill_time = 0
            self.machine_work_time = [0 for _ in range(MATRIX_SIZE)]
            self.process_ids = [0 for _ in range(MATRIX_SIZE)]
            self.end_time = [[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
            self.start_time = [[0 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
    
    
    # 遗传算法实现
    class GA:
        def __init__(self, population_number = 50, times = 10, cross_probability = 0.95,
                     mutation_probability = 0.05, workpiece_number = 0, machine_number = 0):
            self.population_number = population_number  # 种群数量
            self.times = times  # 遗传代数
            self.cross_probability = cross_probability  # 交叉概率
            self.mutation_probability = mutation_probability  # 突变概率
    
            self.workpiece_number = workpiece_number  # 工件数量
            self.machine_number = machine_number  # 机器数量
            self.process_number: int = 0  # 工序数量
            self.chromosome_size: int = 0  # 染色体长度
    
            self.machine_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
            self.time_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
            self.process_matrix = [[-1 for _ in range(MATRIX_SIZE)] for _ in range(MATRIX_SIZE)]
    
            self.genes: Set[Gene] = set()
    
        # 评估染色体
        def evaluate_gene(self, g: Gene) -> GeneEvaluation:
            evaluation = GeneEvaluation()
            # print(g.chromosome)
            for workpiece_id in g.chromosome:
                process_id = evaluation.process_ids[workpiece_id]
                machine_id = self.machine_matrix[workpiece_id][process_id]
                time = self.time_matrix[workpiece_id][process_id]
                evaluation.process_ids[workpiece_id] += 1
                evaluation.start_time[workpiece_id][process_id] = evaluation.machine_work_time[machine_id] \
                    if process_id == 0 else max(evaluation.end_time[workpiece_id][process_id - 1],
                                                evaluation.machine_work_time[machine_id])
                evaluation.machine_work_time[machine_id] = evaluation.start_time[workpiece_id][process_id] + time
                evaluation.end_time[workpiece_id][process_id] = evaluation.machine_work_time[machine_id]
                evaluation.fulfill_time = max(evaluation.fulfill_time, evaluation.machine_work_time[machine_id])
            return evaluation
    
        # 计算适应度
        def calculate_fitness(self, g: Gene) -> float:
            return 1 / self.evaluate_gene(g).fulfill_time
    
        # 个体交叉
        def gene_cross(self, g1: Gene, g2: Gene) -> tuple:
            chromosome_size = self.chromosome_size
    
            def gene_generate(father: Gene, mother: Gene) -> Gene:
                index_list = list(range(chromosome_size))
                p1 = index_list.pop(randint(0, len(index_list) - 1))
                p2 = index_list.pop(randint(0, len(index_list) - 1))
                start = min(p1, p2)
                end = max(p1, p2)
                prototype = father.chromosome[start: end + 1]
                t = mother.chromosome[0:]
                for v1 in prototype:
                    for i in range(len(t)):
                        if v1 == t[i]:
                            t.pop(i)
                            break
                child = Gene()
                child.chromosome = t[0: start] + prototype + t[start:]
                child.fitness = self.calculate_fitness(child)
                return child
    
            return gene_generate(g1, g2), gene_generate(g2, g1)
    
        # 突变
        def gene_mutation(self, g: Gene, n = 2) -> None:
            index_list = [i for i in range(self.chromosome_size)]
            for i in range(n):
                a = index_list.pop(randint(0, len(index_list) - 1))
                b = index_list.pop(randint(0, len(index_list) - 1))
                g.chromosome[a], g.chromosome[b] = g.chromosome[b], g.chromosome[a]
    
            g.fitness = self.calculate_fitness(g)
    
        # 初始化种群 [0, 1, 2, 1, 2, 0, 0, 1] => 12
        def init_population(self):
            for _ in range(self.population_number):
                g = Gene()
                size = self.workpiece_number * self.machine_number
                # print(self.workpiece_number, self.machine_number)
                index_list = list(range(size))
                chromosome = [-1 for _ in range(size)]
                for j in range(self.workpiece_number):
                    for k in range(self.machine_number):
                        index = randint(0, len(index_list) - 1)
                        val = index_list.pop(index)
                        if self.process_matrix[j][k] != -1:
                            chromosome[val] = j
                g.chromosome = list(filter(lambda x: x != -1, chromosome))
                # print("chromosome:", g.chromosome)
                g.fitness = self.calculate_fitness(g)
                self.genes.add(g)
    
        # 选择个体,锦标赛法
        def select_gene(self, n: int = 3):
    
            if len(self.genes) <= 3:
                best_gene = Gene(0)
                for g in self.genes:
                    if g.fitness > best_gene.fitness:
                        best_gene = g
                return best_gene
    
            index_list = list(range(len(self.genes)))
            index_set = {index_list.pop(randint(0, len(index_list) - 1)) for _ in range(n)}
            best_gene = Gene(0)
            i = 0
            for gene in self.genes:
                if i in index_set:
                    if best_gene.fitness < gene.fitness:
                        best_gene = gene
                i += 1
            return best_gene
    
        # 遗传算法
        def exec(self, parameter: List[List[Tuple]]) -> GeneEvaluation:
            # print(parameter)
            workpiece_size = len(parameter)
            for i in range(workpiece_size):
                self.chromosome_size += len(parameter[i])
                self.process_number = max(self.process_number, len(parameter[i]))
                for j in range(len(parameter[i])):
                    self.machine_matrix[i][j] = parameter[i][j][0]
                    self.time_matrix[i][j] = parameter[i][j][1]
    
            for i in range(workpiece_size):
                for j in range(self.process_number):
                    if self.machine_matrix[i][j] != -1:
                        self.process_matrix[i][self.machine_matrix[i][j]] = j
    
            self.init_population()
    
            for _ in range(self.times):
                probability = randint(1, 100) / 100
                if probability < self.mutation_probability:
                    index = randint(0, len(self.genes))
                    i = 0
                    for gene in self.genes:
                        if i == index:
                            self.gene_mutation(gene)
                            break
                        i += 1
                else:
                    g1, g2 = self.select_gene(), self.select_gene()
                    children = self.gene_cross(g1, g2)
                    self.genes.update({*children})
    
            best_gene = Gene(0)
            for gene in self.genes:
                if best_gene.fitness < gene.fitness:
                    best_gene = gene
    
            return self.evaluate_gene(best_gene)
    
    
    ResultData = namedtuple("ResultData", ["fulfill_time", "row_data", "json_data"])
    
    
    # 输出结果
    def schedule(data) -> ResultData:
        print(data)
        reshape = reshape_data(data)
        parameter = reshape.result
        print(parameter)
        n = len(reshape.workpiece)
        m = len(reshape.machine)  # number from 0
        print(m)
        ga = GA(workpiece_number = n, machine_number = m)
        result = ga.exec(parameter)
        p = ga.process_number
        machine_matrix = ga.machine_matrix
        row_data = []
        for i in range(n):
            for j in range(p):
                if machine_matrix[i][j] != -1:
                    temp = {
                        "workpiece": reshape.workpiece[i],
                        "process": reshape.process[i][j],
                        "machine": reshape.machine[machine_matrix[i][j]],
                        "startTime": result.start_time[i][j],
                        "endTime": result.end_time[i][j]
                    }
                    # print(i, j, machine_matrix[i][j], result.start_time[i][j], result.end_time[i][j])
                    row_data.append(temp)
    
        json_data = {}
        for i in range(n):
            for j in range(p):
                if machine_matrix[i][j] != -1:
                    temp = {
                        "workpiece": reshape.workpiece[i],
                        "process": reshape.process[i][j],
                        "startTime": result.start_time[i][j],
                        "endTime": result.end_time[i][j]
                    }
                    m = reshape.machine[machine_matrix[i][j]]
                    if m not in json_data:
                        json_data[m] = [temp]
                    else:
                        json_data[m].append(temp)
        return ResultData(result.fulfill_time, row_data, json_data)
    
    
    if __name__ == "__main__":
        # 测试数据
        d = [{'workpiece': '#W-89-10', 'process': '#P-1349-31', 'machine': '#M-8763-12', 'time': 10, 'order': 0},
             {'workpiece': '#W-89-10', 'process': '#P-6261-32', 'machine': '#M-2304-14', 'time': 21, 'order': 1},
             {'workpiece': '#W-89-10', 'process': '#P-6917-33', 'machine': '#M-6360-16', 'time': 12, 'order': 2},
             {'workpiece': '#W-5863-13', 'process': '#P-2772-34', 'machine': '#M-6557-17', 'time': 21, 'order': 0},
             {'workpiece': '#W-5863-13', 'process': '#P-468-35', 'machine': '#M-8763-12', 'time': 21, 'order': 1},
             {'workpiece': '#W-5829-8', 'process': '#P-3959-28', 'machine': '#M-2304-14', 'time': 5, 'order': 2},
             {'workpiece': '#W-5829-8', 'process': '#P-5852-27', 'machine': '#M-671-13', 'time': 11, 'order': 1},
             {'workpiece': '#W-5829-8', 'process': '#P-7792-26', 'machine': '#M-8763-12', 'time': 10, 'order': 0},
             {'workpiece': '#W-554-9', 'process': '#P-6810-29', 'machine': '#M-671-13', 'time': 5, 'order': 0}]
        print(schedule(d).row_data)
    

    工具reshape_data函数实现 

    from typing import (List, Dict)
    from collections import namedtuple
    
    test_data = [{"workpiece": '#W-5829-8',
                  "process": '#P-3959-28',
                  "machine": '#M-2304-14',
                  "time": 5,
                  "order": 2},
                 {"workpiece": '#W-5829-8',
                  "process": '#P-5852-27',
                  "machine": '#M-671-13',
                  "time": 11,
                  "order": 1},
                 {"workpiece": '#W-5829-8',
                  "process": '#P-7792-26',
                  "machine": '#M-8763-12',
                  "time": 10,
                  "order": 0},
                 {"workpiece": '#W-554-9',
                  "process": '#P-6810-29',
                  "machine": '#M-671-13',
                  "time": 5,
                  "order": 0},
                 {"workpiece": '#W-554-9',
                  "process": '#P-8883-30',
                  "machine": '#M-3836-15',
                  "time": 10,
                  "order": 1}]
    
    ReshapeData = namedtuple("ReshapeData",
                             ["result", "workpiece", "machine", "process", "reverse_workpiece", "reverse_machine"])
    
    
    def make_reverse_index(arr: list) -> dict:
        result = {}
        for i in range(len(arr)):
            result[arr[i]] = i
        return result
    
    
    def filter_value(origin: list, except_value: int) -> list:
        return list(filter(lambda v: v != except_value, origin))
    
    
    def reshape_data(data: List[Dict]) -> ReshapeData:
        def make_array(r: dict) -> ReshapeData:
            workpieces = list(set(map(lambda v: v["workpiece"], data)))
            machines = list(set(map(lambda v: v["machine"], data)))
            process = [-1 for _ in workpieces]
            reverse_workpieces = make_reverse_index(workpieces)
            reverse_machines = make_reverse_index(machines)
            ans = [-1 for _ in r.keys()]
    
            for key, val in r.items():
                # print(val, type(val))
                m = max(*map(lambda v: v["order"], val)) + 1 if len(val) > 1 else val[0]["order"]
                t = [-1 for _ in range(m + 1)]
                x = [-1 for _ in range(m + 1)]
                for p in val:
                    t[p["order"]] = (reverse_machines[p["machine"]], p["time"])
                    x[p["order"]] = p["process"]
                x = filter_value(x, -1)
                t = filter_value(t, -1)
                if ans[reverse_workpieces[key]] == -1:
                    ans[reverse_workpieces[key]] = t
                else:
                    ans[reverse_workpieces[key]].append(t)
    
                process[reverse_workpieces[key]] = x
            process = filter_value(process, -1)
            ans = filter_value(ans, -1)
            return ReshapeData(ans, workpieces, machines, process, reverse_machines, reverse_workpieces)
    
        result = {}
        for value in data:
            w = value["workpiece"]
            if w in result:
                result[w].append(value)
            else:
                result[w] = [value]
        # print(result)
        return make_array(result)
    
    
    if __name__ == "__main__":
        print(reshape_data(test_data).result)
        print(reshape_data(test_data).machine)
    

     同理Java也很容易实现:

    import java.util.*;
    
    class GeneticAlgorithm {
        private final int populationNumber = 60;
        private final double crossProbability = 0.95;
        private final double mutationProbability = 0.05;
        private int jobNumber;
        private int machineNumber;
        private int processNumber;
        private int chromosomeSize;
    
        private int[][] machineMatrix = new int[1024][1024];
        private int[][] timeMatrix = new int[1024][1024];
        private int[][] processMatrix = new int[1024][1024];
    
    
        private Set<Gene> geneSet = new HashSet<>();
        private Random random = new Random();
        public GeneticAlgorithm(int jobNumber, int machineNumber) {
            this.jobNumber = jobNumber;
            this.machineNumber = machineNumber;
            for (int[] matrix : this.machineMatrix) Arrays.fill(matrix, -1);
            for (int[] process : this.processMatrix) Arrays.fill(process, -1);
        }
    
        private List<Integer> makeList(int n) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < n; i++) result.add(i);
            return result;
        }
    
        private Integer[] filterArray(Integer[] arr, int filterVal) {
            List<Integer> result = new ArrayList<>();
            for (int i = 0; i < arr.length; i++) {
                if (arr[i] != filterVal) {
                    result.add(arr[i]);
                }
            }
            return result.toArray(new Integer[0]);
        }
    
        // 初始化种群
        public  void initialPopulation() {
            for (int i = 0; i < populationNumber; i ++) {
                Gene g = new Gene();
                int size = jobNumber * machineNumber;
                List<Integer> indexList = makeList(size);
                Integer[] chromosome = new Integer[size];
                Arrays.fill(chromosome, -1);
                for (int j = 0; j < jobNumber; j++) {
                    for (int k = 0; k < machineNumber; k ++) {
                        int index = random.nextInt(indexList.size());
                        int val = indexList.remove(index);
                        if (processMatrix[j][k] != -1) {
                            chromosome[val] = j;
                        }
                    }
                }
                g.chromosome = filterArray(chromosome, -1);
                g.fitness = calculateFitness(g).fulfillTime;
                geneSet.add(g);
            }
        }
    
        public List<Integer> subArray(Integer[] arr, int start, int end) {
            List<Integer> list = new ArrayList<>();
            for (int i = start; i < end; i++) list.add(arr[i]);
            return list;
        }
        
        // 计算适应度
        public Result calculateFitness(Gene g) {
            Result result = new Result();
            for (int i = 0; i < g.chromosome.length; i ++) {
                int jobId = g.chromosome[i];
                int processId = result.processIds[jobId];
                int machineId = machineMatrix[jobId][processId];
                int time = timeMatrix[jobId][processId];
                result.processIds[jobId] += 1;
                result.startTime[jobId][processId] = processId ==0 ? result.machineWorkTime[machineId] :
                        Math.max(result.endTime[jobId][processId - 1], result.machineWorkTime[machineId]);
                result.machineWorkTime[machineId] = result.startTime[jobId][processId] + time;
                result.endTime[jobId][processId] = result.machineWorkTime[machineId];
                result.fulfillTime = Math.max(result.fulfillTime, result.machineWorkTime[machineId]);
    
            }
            return result;
        }
        // 交叉算子
        private Gene crossGene(Gene g1, Gene g2) {
            List<Integer> indexList = makeList(chromosomeSize);
            int p1 = indexList.remove(random.nextInt(indexList.size()));
            int p2 = indexList.remove(random.nextInt(indexList.size()));
    
            int start = Math.min(p1, p2);
            int end = Math.max(p1, p2);
    
            List<Integer> proto = subArray(g1.chromosome, start, end + 1);
            List<Integer> t = new ArrayList<>();
            for (Integer c : g2.chromosome) t.add(c);
            for (Integer val : proto) {
                for (int i = 0; i < t.size(); i++) {
                    if (val.equals(t.get(i))) {
                        t.remove(i);
                        break;
                    }
                }
            }
    
            Gene child = new Gene();
            proto.addAll(t.subList(start, t.size()));
            List<Integer> temp = t.subList(0, start);
            temp.addAll(proto);
            child.chromosome = temp.toArray(new Integer[0]);
            child.fitness = (double) calculateFitness(child).fulfillTime;
            return child;
        }
        // 突变算子
        public Gene mutationGene(Gene gene, int n) {
            List<Integer> indexList = makeList(chromosomeSize);
            for (int i = 0; i < n; i++) {
                int a = indexList.remove(random.nextInt(indexList.size()));
                int b = indexList.remove(random.nextInt(indexList.size()));
                int t = gene.chromosome[a];
                gene.chromosome[a] = gene.chromosome[b];
                gene.chromosome[b] = t;
            }
            gene.fitness = calculateFitness(gene).fulfillTime;
            return gene;
        }
    
        // 选择个体
        public Gene selectGene(int n) {
            List<Integer> indexList = makeList(geneSet.size());
            Map<Integer, Boolean> map = new HashMap<>();
            for (int i = 0; i < n; i++) {
                map.put(indexList.remove(random.nextInt(indexList.size())), true);
            }
            Gene bestGene = new Gene(0xfffff);
            int i = 0;
            for (Gene gene : geneSet) {
                if (map.containsKey(i)) {
                    if (bestGene.fitness > gene.fitness) {
                        bestGene = gene;
                    }
                }
                i ++;
            }
            return bestGene;
        }
    
        public Result run(List<List<Integer[]>> job) {
            int jobSize = job.size();
    
            for (int i = 0; i < jobSize; i ++) {
                chromosomeSize += job.get(i).size();
                processNumber = Math.max(processNumber, job.get(i).size());
                for (int j = 0; j < job.get(i).size(); j ++) {
                    machineMatrix[i][j] = job.get(i).get(j)[0];
                    timeMatrix[i][j] = job.get(i).get(j)[1];
    
                }
            }
    
            for (int i = 0; i < jobSize; i++) {
                for (int j = 0;j < processNumber; j++){
                    if (machineMatrix[i][j] != -1) {
                        processMatrix[i][machineMatrix[i][j]] = j;
                    }
                }
            }
            initialPopulation();
            for (int i = 0; i < populationNumber; i++) {
                double p = (double) random.nextInt(100) / 100.0;
                if (p < mutationProbability) {
                    int index = random.nextInt(geneSet.size());
                    int k = 0;
                    for (Gene gene : geneSet) {
                        if (k == index) {
                            mutationGene(gene);
                            break;
                        }
                        k ++;
                    }
                } else {
                    Gene g1 = selectGene(), g2 = selectGene();
                    Gene child1 = crossGene(g1, g2), child2 = crossGene(g2, g1);
                    geneSet.add(child1);
                    geneSet.add(child2);
                }
            }
            Gene bestGene = new Gene(0xffffff);
            for (Gene gene : geneSet) {
                if (bestGene.fitness > gene.fitness) {
                    bestGene = gene;
                }
            }
            return calculateFitness(bestGene);
        }
    
        public Gene selectGene() {
            return selectGene(3);
        }
    
        public Gene mutationGene(Gene gene) {
            return mutationGene(gene, 2);
        }
    
        static public void main(String[] args) {
            List<List<Integer[]>> job = Arrays.asList(
                    Arrays.asList(new Integer[]{0, 3}, new Integer[]{1, 2}, new Integer[]{2, 2}),
                    Arrays.asList(new Integer[]{0, 2}, new Integer[]{2, 1}, new Integer[]{1, 4}),
                    Arrays.asList(new Integer[]{1, 4}, new Integer[]{2, 3})
            );
    
            int n = 3, m = 3;
            GeneticAlgorithm ga = new GeneticAlgorithm(n, m);
            Result result = ga.run(job);
            int processNumber = ga.processNumber;
    
            int[][] machineMatrix = ga.machineMatrix;
            System.out.println(result.fulfillTime);
    
            for (int i = 0; i < n; i++) {
                for (int j = 0 ; j < processNumber; j++) {
                    if (machineMatrix[i][j] != -1) {
                        System.out.println(String.format("job: %d, process: %d, machine: %d, startTime: %d, endTime: %d",
                                i, j, machineMatrix[i][j], result.startTime[i][j], result.endTime[i][j]));
                    }
                }
            }
        }
    }
    
    
    
    class Gene {
        public double fitness;
        public Integer[] chromosome;
        public Gene() {
            fitness = 0;
        }
        public Gene(double fitness) {this.fitness = fitness;}
    }
    
    class Result {
        public int fulfillTime = 0;
        public int[] machineWorkTime = new int[1024];
        public int[] processIds = new int[1024];
        public int[][] endTime = new int[1024][1024];
        public int[][] startTime = new int[1024][1024];
    }

    基于Electron的作业车间调度系统实现

    写了那么多的遗传算法解作业车间调度问题,当然还要有实际应用了,因此开发了一个作业车间调度系统,核心功能很简单就是对工件、机器、工序进行增删改查并使用遗传算法计算调度结果,前端用甘特图展示调度结果。(GitHub地址:https://github.com/sundial-dreams/BitMESClient,如果觉得项目不错,别忘了点赞哦)

    系统总体技术路线:采用前后端分离模式开发,基于C/S模式,客户端使用JavaScript,Electron, React,Node.js等进行组件化开发,服务端使用express,nodejs,typescript,python,sanic,graphql等开发独立的graphql服务或http服务,数据库使用mysql来存储基本的信息,redis来实现id生成,mongodb来存储调度结果。

    1. Client端:使用JavaScript来开发PC端应用程序。基于Electron进行开发,在Electron基础上使用React、Redux、Antd、Echarts等前端技术和包,以模块化、组件化的方式构建一个独立的UI页面,对于页面的切换使用了前端路由React-router。除此之外,通过封装一个GraphQL类来做GraphQL查询,以此和后端进行数据交互。通过这种方式能快速的构建一个可维护性好,UI美观的PC端应用程序。

    2. GrapgQL Service端:使用Typescript开发的一个GraphQL服务,提供GraphQL查询。基于NodeJS、Express、GraphQL等来构建一个GraphQL服务器,由于Node.js的异步非阻塞特性,使得构建的服务器并发能力更强。除此之外,使用TypeORM来做数据库的对象关系映射,加快开发速度。通过这种方式能快速搭建起一个GraphQL服务端,使用GraphQL查询来替代传统的RESTful API能使提供的API服务可维护性、扩展性更强。

    3. Schedule Service端:使用Python开发,提供作业调度服务。基于Python异步Web框架Sanic,使得构建的服务器运行效率和并发能力都比较强,并且使用Python来实现作业车间调度算法(遗传算法)一方面是比较容易,另一方面是Python支持多线程编程,因此多线程来优化算法也能实现。

    4. Data Storage端:数据存储,使用MySQL来存储一些基本的数据,如机器信息、工件信息、工件工艺信息、员工信息等等。使用Redis来存储一些健值对信息以及Id生成,由于Redis的单线程异步非阻塞特性,使得生成的Id不存在重复。使用MongoDB来存储调度结果,由于调度结果完全是JSON格式数据,与使用MySQL存储相比,使用文档数据库MongoDB来存储比较容易,而且查询也比较方便。

    项目运行:

    首页

    管理

    作业调度 

    最后,如果觉得这篇文章有帮助,别忘了点赞哦

    展开全文
  • 图像检索(含代码

    千次阅读 2020-06-01 00:00:20
    中国最大的电子商务系统淘宝网的后端系统上保存着286亿多张图片。针对这些包含丰富视觉信息的海量图片,如何在这些浩瀚的图像库中方便、快速、准确地查询并检索到用户所需的或感兴趣的图像,成为多媒体信息检
  • 如图2所示,令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。 三、限流工具类RateLimiter Google开源工具包...
  • c++实现学生信息管理系统

    千次阅读 2020-06-01 19:10:36
    实验内容: 对学生信息管理系统,要求完成以下基本任务: 1.改写程序为良好程序风格(文档注释,函数注释,语句注释)。 2.将功能补充完全(基于文件处理,完成...概要设计(包括数据结构及算法绘制流程图或伪代码表示)
  • 算法设计与分析】经典常考三十三道例题&AC代码

    千次阅读 多人点赞 2021-11-13 14:08:08
    下文会给出机试的33道题目&AC代码&注释供大家参考。 《算法设计与分析》用的是屈婉玲老师的教材,上机习题用的是王晓东前辈的,开授这门课的教授表示:考虑到算法具有一定的难度,并不适合所有的学生,只讲授和...
  • 目前为止,我们已经推出了《从零开始学习 深度学习》和《从零开始学习模型部署》系列教程,方便大家入门算法开发。 欢迎大家进抠抠裙: deeplearningYYDS裙3:1015081610 威信裙需先jia个人威信:deeplearningYYDS 经...
  •   在GC 中最重要的算法就是GC标记-清除算法(Mark-Sweep GC)。在很多的场景下都还是在使用这个算法来进行垃圾回收操作。 什么是GC标记-清除算法   GC标记清除是由两个阶段构成的,一个是标记阶段,就是把所有...
  • 编程算法同步入门

    千次阅读 2019-05-29 23:30:03
    原因是,复杂软件的功能太多,如果所有功能都用一个程序来实现,会导致这个程序的源代码过多,程序结构很难清晰,管理和维护起来的成本太高。 等等,这里怎么又出来了一个“程序的源代码“,它和程序不是一回事嘛?...
  • Deep-Sort多目标追踪算法代码解析

    万次阅读 多人点赞 2020-05-07 13:21:46
    Deep SORT是多目标跟踪(Multi-Object Tracking)中常用到的一种算法,是一个Detection Based Tracking的方法。这个算法工业界关注度非常高,在知乎上有很多文章都是使用了Deep SORT进行工程部署。 1. MOT主要步骤 在...
  • (转载)堪称最好的A*算法

    千次阅读 2018-01-16 20:31:20
    如此好贴,不能不转!...本文版权归原作者、译者所有,我只是转贴;...基本上,这文章可以说是最佳A*算法文档。极力推荐! Amit’s A star Page中译文   译序 这篇文章很适合A*算法的初学者,可惜网上没找到翻
  • 是一场比工业化更加深刻和更加广泛的社会变革,它要求在产品或服务的生产过程中实现管理流程、 组织机构、生产技能和生产工具的变革。 2、信息 是一种客观事物,它与材料、能源一样,都是社会的基础资源。 3、...
  • 开源主流分布式文件系统简单介绍

    千次阅读 2021-02-01 11:16:32
    一、分布式文件系统简介 1.特点 2.主要指标及分类对比 3.AFS与NFS 二、开源分布式文件系统 1.GFS (1)GFS与NFS,AFS的区别 (2)BigTable (3)Chubby (4)特点1 2.HDFS (1...
  • LRU和LFU 算法(页面置换算法

    万次阅读 2022-02-27 02:42:29
    LRU和LFU都是内存管理的页面置换算法。 LRU:最近最少使用(最长时间)淘汰算法(Least Recently Used)。LRU是淘汰最长时间没有被使用的页面。 LFU:最不经常使用(最少次)淘汰算法(Least Frequently Used)。LFU是...
  • 入门《大话数据结构 程杰》《算法图解》《数据结构与算法分析:Java语言描述》(大学课本 伪代码)《剑指offer》《编程珠玑》(对大数据量处理的算法)《编程之美》(超级难)《算法导论》(很厚很无聊)《算法第四版》(推荐...
  • RSA加解密算法数学基础及python实现

    千次阅读 2020-07-16 08:24:52
    使用python实现RSA算法,先简单的对RSA进行说明: 在对称密码体制中,密钥分发过程复杂,代价高;密钥量增大造成密钥管理困难;保密通信系统的开放性差;如果收发双方素不相识,或没有可靠的密钥传递渠道,则无法...
  • 【综合实训】图书管理系统——详细设计说明书

    千次阅读 多人点赞 2021-05-07 18:49:04
    文章目录1 引言1.1 编写目的1.2 项目背景1.3 定义1.4 参考资料2 总体设计2.1 需求概述2.2 ...以下叙述将结合文字描述、伪代码,图表等来描述高校图书管理系统的详细设计和相关的模块描述。本报告的预期读者有客户、项
  • 2.4.5 用伪代码表示算法 30 2.4.6 用计算机语言表示算法 31 2.5 结构化程序设计方法 31 3 数据类型、运算符与表达式 3.1 C语言的数据类型 32 3.2 常量与变量 33 23.2.1 常量和符号常量 33 3.2.2 变量 33 3.3 整型...
  • Deep SORT多目标跟踪算法代码解析

    千次阅读 多人点赞 2020-04-20 11:51:33
    Deep SORT是多目标跟踪(Multi-Object Tracking)中常用到的一种算法,是一个Detection Based Tracking的方法。...代码)对Deep SORT算法进行代码层面的解析。 在之前笔者写的一篇Deep SORT论文阅读总结中...
  • 操作系统课程设计 超市购物模拟 组别: 组员: 编程 设计报告 汇报 , PPT...
  • Linux驱动开发_设备文件系统详解

    千次阅读 多人点赞 2021-05-11 14:09:24
    以上的前提下是你的设备是流行设备且被操作系统的设备管理器支持的情况下,倘若我们有一个未知的设备,或者是我自己开发的硬件产品,如我们自己写的键盘,我们不使用通用键盘通讯协议,我们非要自己创建一套我们键盘...
  • 该飞机订票系统主要实现了对机票的一些基本信息进行存储和管理的功能。在系统实现了对机票信息的增删改查,考虑到查询的方便性,对机票按照航班号进行排序,而此排序方法用并行快速排序运用进来。利用OpenMP的并行...
  • 关于若干选举算法的解释与实现

    千次阅读 2016-08-24 22:44:22
    分布式中有这么一个疑难问题,客户端向一个分布式集群的服务端...要确保数据一致,需要选举算法的支撑,这就引申出了今天我们要讨论的题目,关于选举算法的原理解释及实现,选举包括对机器的选举,也包括对消息的选举。
  • python(3):python的优缺点

    千次阅读 2020-12-22 13:32:27
    Python的这种伪代码本质是它最大的优点之一。它使你能够专注于解决问题而不是去搞明白语言本身。2.易学就如同你即将看到的一样,Python极其容易上手。前面已经提到了,Python有极其简单的语法。3.免费、开源Python是...
  • 内容管理系统CMS学习总结

    千次阅读 2016-09-01 14:17:28
    CMS (内容管理系统) CMS是Content Management System的缩写,意为"内容管理系统"。 内容管理系统是企业信息化建设和电子政务的新宠,也是一个相对较新的市场。对于内容管理,业界还没有一个统一的定义,不同的...
  • C语言课设销售管理系统设计

    万次阅读 多人点赞 2016-05-26 09:21:01
    该设计要求学生以某公司销售管理业务为背景,设计、开发一套“销售管理系统”软件。 通过该题目的设计过程,可以培养学生结构化程序设计的思想,加深对高级语言基本语言要素和控制结构的理解,针对c语言中的重点和...
  • 操作系统之进程管理习题

    千次阅读 2021-12-11 22:19:54
    操作系统进程管理习题详解
  • 加密算法与随机数

    千次阅读 2020-04-30 18:04:12
    常见的加密算法分为分组加密算法和流加密算法两种,两者的实现原理不同。 1)分组加密算法基于分组(block)进行操作,根据算法的不同,每个分组的长度可能不同。分组加密算法的代表有DES 3-DES Blowfish IDEA AES...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 34,716
精华内容 13,886
热门标签
关键字:

文件管理系统算法的伪代码实现