遗传算法研究论文

遗传算法研究论文

遗传算法应用于图像匹配的最早论文是由美国科学家戴维·戈德伯格（David Goldberg）在1988年发表的论文《基于遗传算法的图像匹配》（"Genetic Algorithms in Search, Optimization, and Machine Learning"）中，提出了一种利用遗传算法进行图像匹配的方法。该方法主要是利用遗传算法对图像特征进行编码，并通过遗传算法的交叉、变异等操作，对不同的图像特征进行优化，从而实现图像匹配的目的。
这篇论文的发表标志着遗传算法在图像处理领域中的首次应用，为后来的相关研究奠定了基础。同时，该论文也表明了遗传算法在解决复杂优化问题中的潜力和优越性，成为了现代遗传算法应用领域的开山之作。

遗传算法研究进展

遗传算法［56，53］研究的兴起是在20世纪80年代末和90年代初期，但它的历史起源可追溯到20世纪60年代初期。早期的研究大多以对自然遗传系统的计算机模拟为主。早期遗传算法的研究特点是侧重于对一些复杂的操作的研究。虽然其中像自动博弈、生物系统模拟、模式识别和函数优化等给人以深刻的印象，但总的来说这是一个无明确目标的发展时期，缺乏带有指导性的理论和计算工具的开拓。这种现象直到20世纪70年代中期由于Holland和De Jong的创造性研究成果的发表才得到改观。当然，早期的研究成果对于遗传算法的发展仍然有一定的影响，尤其是其中一些有代表性的技术和方法已为当前的遗传算法所吸收和发展。

在遗传算法作为搜索方法用于人工智能系统中之前，已有不少生物学家用计算机来模拟自然遗传系统。尤其是Fraser的模拟研究，他于1962年提出了和现在的遗传算法十分相似的概念和思想。但是，Fraser和其他一些学者并未认识到自然遗传算法可以转化为人工遗传算法。Holland教授及其学生不久就认识到这一转化的重要性，Holland认为比起寻找这种或那种具体的求解问题的方法来说，开拓一种能模拟自然选择遗传机制的带有一般性的理论和方法更有意义。在这一时期，Holland不但发现了基于适应度的人工遗传选择的基本作用，而且还对群体操作等进行了认真的研究。1965年，他首次提出了人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。

1967年，Bagley在他的论文中首次提出了遗传算法（genetic algorithm）这一术语，并讨论了遗传算法在自动博弈中的应用。他所提出的包括选择、交叉和变异的操作已与目前遗传算法中的相应操作十分接近。尤其是他对选择操作做了十分有意义的研究。他认识到，在遗传进化过程的前期和后期，选择概率应合适地变动。为此，他引入了适应度定标（scaling）概念，这是目前遗传算法中常用的技术。同时，他也首次提出了遗传算法自我调整概念，即把交叉和变异的概率融于染色体本身的编码中，从而可实现算法自我调整优化。尽管Bagley没有对此进行计算机模拟实验，但这些思想对于后来遗传算法的发展所起的作用是十分明显的。

在同一时期，Rosenberg也对遗传算法进行了研究，他的研究依然是以模拟生物进化为主，但他在遗传操作方面提出了不少独特的设想。1970年Cavicchio把遗传算法应用于模式识别中。实际上他并未直接涉及到模式识别，而仅用遗传算法设计一组用于识别的检测器。Cavicchio对于遗传操作以及遗传算法的自我调整也做了不少有特色的研究。

Weinberg于1971年发表了题为《活细胞的计算机模拟》的论文。由于他和Rosenberg一样注意于生物遗传的模拟，所以他对遗传算法的贡献有时被忽略。实际上，他提出的多层次或多级遗传算法至今仍给人以深刻的印象。

第一个把遗传算法用于函数优化的是Hollstien。1971年他在论文《计算机控制系统中的人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。实际上，他主要是讨论了对于二变量函数的优化问题。其中，对于优势基因控制、交叉和变异以及各种编码技术进行了深入的研究。

1975年在遗传算法研究的历史上是十分重要的一年。这一年，Holland出版了他的著名专著《自然系统和人工系统的适配》。该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（schemata theory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。直到这时才知道遗传操作到底在干什么，为什么又干得那么出色，这对于以后陆续开发出来的遗传操作具有不可估量的指导作用。

同年，De Jong完成了他的重要论文《遗传自适应系统的行为分析》。他在该论文中所做的研究工作可看作是遗传算法发展进程中的一个里程碑，这是因为他把Holland的模式理论与他的计算实验结合起来。尽管De Jong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generation gap）等新的遗传操作技术。可以认为，De Jong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论迄今仍具有普遍的指导意义。

进入20世纪80年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。尤其是遗传算法的应用研究显得格外活跃，不但它的应用领域扩大，而且利用遗传算法进行优化和规则学习的能力也显著提高，同时产业应用方面的研究也在摸索之中。此外一些新的理论和方法在应用研究中亦得到了迅速的发展，这些无疑均给遗传算法增添了新的活力。

随着应用领域的扩展，遗传算法的研究出现了几个引人注目的新动向：一是基于遗传算法的机器学习（Genetic Base Machine Learning），这一新的研究课题把遗传算法从历来离散的搜索空间的优化搜索算法扩展到具有独特的规则生成功能的崭新的机器学习算法。这一新的学习机制对于解决人工智能中知识获取和知识优化精炼的瓶颈难题带来了希望。二是遗传算法正日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合，这对开拓21世纪中新的智能计算技术将具有重要的意义。三是并行处理的遗传算法的研究十分活跃。这一研究不仅对遗传算法本身的发展，而且对于新一代智能计算机体系结构的研究都是十分重要的。四是遗传算法和另一个称为人工生命的崭新研究领域正不断渗透。所谓人工生命即是用计算机模拟自然界丰富多彩的生命现象，其中生物的自适应、进化和免疫等现象是人工生命的重要研究对象，而遗传算法在这方面将会发挥一定的作用。五是遗传算法和进化规划（Evolution Programming，EP）以及进化策略（Evolution Strategy，ES）等进化计算理论日益结合。EP和ES几乎是和遗传算法同时独立发展起来的，同遗传算法一样，它们也是模拟自然界生物进化机制的智能计算方法，既同遗传算法具有相同之处，也有各自的特点。

随着遗传算法研究和应用的不断深入和发展，一系列以遗传算法为主题的国际会议十分活跃。从1985年开始，国际遗传算法会议，即ICGA（International Conference on Genetic Algorithm）每两年举行一次。在欧洲，从1990年开始也每隔一年举办一次类似的会议，即 PPSN（Parallel Problem Solving from Nature）会议。除了遗传算法外，大部分有关ES和EP的学术论文也出现在PPSN中。另外，以遗传算法的理论基础为中心的学术会议有FOGA（Foundation of Genetic Algorithm）。它也是从1990年开始，隔年召开一次。这些国际学术会议论文集中反映了遗传算法近些年来的最新发展和动向。

近些年将遗传算法应用于图像匹配的论文推荐？

以下是近些年将遗传算法应用于图像匹配的一些论文推荐：

C语言遗传算法在求解TSP问题 毕业论文+源代码

目
录
摘要
I
Abstract
II
引
言
1
第一章
基本遗传算法
2
1.1
遗传算法的产生及发展
3
1.2
基本原理
3
1.3
遗传算法的特点
3
1.4
基本遗传算法描述
5
1.5
遗传算法构造流程
6
第二章
遗传算法的实现技术
6
2.1
编码方法
7
2.1.1
二进制编码
7
2.1.2
格雷码编码
7
2.1.3
符点数编码
8
2.1.4
参数编码
8
2.2
适应度函数
10
2.3
选择算子
10
2.4
交叉算子
10
2.4.1
单点交叉算子
10
2.4.2
双点交叉算子
11
2.4.3
均匀交叉算子
11
2.4.4
部分映射交叉
11
2.4.5
顺序交叉
12
2.5
变异算子
12
2.6
运行参数
12
2.7
约束条件的处理方法
13
2.8
遗传算法流程图
14
第三章
遗传算法在TSP上的应用
15
3.1
TSP问题的建模与描述
15
3.2
对TSP的遗传基因编码方法
16
3.3
针对TSP的遗传操作算子
17
3.3.1
选择算子
17
3.3.1.1
轮盘赌选择
17
3.3.1.2
最优保存策略选择
17
3.3.2
交叉算子
20
3.3.2.1
单点交叉
20
3.3.2.2
部分映射交叉
21
3.3.3
变异算子
23
3.4
TSP的混和遗传算法
26
第四章
实例分析
27
4.1
测试数据
27
4.2
测试结果
27
4.3
结果分析
27
摘
要
TSP
(Traveling
Salesman
Problem)旅行商问题是一类典型的NP完全问题，遗传算法是解决NP问题的一种较理想的方法。文章首先介绍了基本遗传算法的基本原理、特点及其基本实现技术；接着针对TSP
问题，论述了遗传算法在编码表示和遗传算子（包括选择算子、交叉算子变异算子这三种算子）等方面的应用情况，分别指出几种常用的编码方法的优点和缺点，并且结合TSP的运行实例详细分析了基本遗传算法的4个运行参数群体大小、遗传算法的终止进化代数、交叉概率、变异概率，对遗传算法的求解结果和求解效率的影响，经过多次的测试设定出了它们一组比较合理的取值。最后，简单说明了混合遗传算法在求解TSP问题中的应用并对遗传算法解决TSP问题的前景提出了展望。
关键词：TSP
遗传算法
遗传算子
编码
@@@需要的话按我的名字找我吧

详谈改进的遗传算法求解柔性作业车间调度问题论文

详谈改进的遗传算法求解柔性作业车间调度问题论文

0 引言

作业车间调度问题(Job-shop scheduling problem，JSP)是研究生产线调度问题最常用的模型之一，也是实现先进制造和提高生产效率的基础和关键. 柔性作业车间调度问题( Flexible jobshopscheduling problem，FJSP)是传统作业车间调度问题的扩展，在传统的作业车间调度问题中，每个工件的加工工序是确定的，每一道工序的加工机器和加工时间也是确定的，而在柔性作业车间调度问题中，每个工件的每一道工序可以在多个可选择的加工机器上进行加工，并且不同的加工机器所需要的加工时间是不同的，增加了调度的灵活性，比较符合生产的实际情况.

柔性作业车间调度问题已经被证明是更复杂的NP-Hard 问题，因而难以取得最优解. 目前，求解FJSP 的常用方法有禁忌搜索( TS)，模拟退火(SA)和遗传算法(GA)等. 其中遗传算法以其操作简单、鲁棒性强、搜索全局最优解速度快等特点，在生产调度领域得到了广泛的应用.

遗传算法是由美国J. Holland 教授于1975 年提出的，是一种模拟自然进化过程的一种优化算法. 由于传统的遗传算法存在着较大的缺陷，国内外学者已从不同角度对其进行了改进，本文对传统遗传算法的初始种群进行了改进，以提高初始解的质量.

1 柔性作业车间调度模型设有n 个待加工工件J(J1，J2，…，Jn)，在m台设备上加工M(M1，M2，…，Mm)，每个工件Ji有Pi(Pi1，Pi2，…，Pin) 道工序，每道工序可在一台或多台设备上加工，同一道工序在不同设备上加工的时间可能不等，工序Pik的可选机器集为Mik(Mik 罬)，每台设备的加工时间从0 开始，加工完所有工件的完成时间为ETMi . 本文以最小化最大完工时间为性能指标，其目标函数为:f(x) = min(max(ETMi))，1 ≤ i ≤ m模型需满足如下约束条件:(1)同一工件的工序加工顺序确定;(2)每道工序必须在它的上一道工序加工完成后才能开始加工;(3)每道工序只能选择一台设备进行操作;(4)每台设备在同一时间只能加工一个工件的一道工序;(5)每道工序在设备上操作时都不允许被中断;(6) 不同工件工序之间没有先后约束条件.一个包含3 个工件、5 台机器的FJSP 的问题.

2 算法的设计

(1) 基因编码

常用的遗传算法编码方案有二进制编码、格雷码编码、矩阵编码、自然数编码等，本文采用自然数编码，每条染色体表示一个可行解，同时采用双层编码，第一层编码为基于工件的工序编码，编码长度为所有工件工序之和，基因值代表工件号，基因值出现的次数代表该工件的工序总数，第二层编码为对应于第一层工件工序的机器编码，所以编码长度也为所有工件工序之和.染色体表示的工序顺序为(O31，O11，O12，O21，O22，O32，O13，O33)，染色体表示的机器序列为(M2，M4，M2，M1，M4，M5，M3，M4).

(2)产生初始种群

初始种群的优良对生物进化会产生很大的影响，本文对初始种群的机器选择进行了改进，首先随机生成初始种群的工序编码，工序编码生成后就要对应生成机器编码，每个工件工序在对应可选机器集中选择机器时，是以不同的概率的来选择不同的机器，机器加工时间短的以大概率被选择，相比之下，机器加工时间长的以小概率被选择，这样既保证了机器选择的随机性，也优化了初始种群.

(3)适应度函数的确定

本文以最小化最大完工时间为目标函数，故选择全部工件完工时间作为评价种群优劣的标准，设n 个待加工工件在m(M1，M2，…，Mm) 台设备上加工，所有加工工件工序在设备上的最后完工时间为ETMi(i = 1，2，…，m)，T = max(ETMi)，则适应度函数fi = 1 /T，T 越小，则适应度越大，即个体越优.

(4)选择

选择操作的目的是为了保留优良个体，使他们可以遗传到下一代. 本文采用精英保留策略和轮盘赌法相结合的方法，对父代个体和子代个体进行选择时直接将最优个体和次优个体遗传到下一代，然后对剩余的个体采用轮盘赌法进行选择，选择出p - 2 个个体到下一代进行遗传操作. 若种群规模为p，个体i 的适应度为fi，则个体i 被选择的概率pi为pi = fi /Σpk = 1fk即适应度越高的个体被选择的概率就越大.

(5)交叉

交叉操作是产生新个体的主要方法，提高全局搜索能力. 本文采用单点交叉方式，即随机产生一个交叉点，交换交叉点后的基因. 从种群中随机选择两个个体，交换两个个体工序编码的交叉点后面的基因，将交叉后工件多余的工序替换为其他工件缺失的工序;机器部分则按交叉前工件工序所选择的机器进行相应调整以保证其子代染色体的`合法性.

(6)变异

变异操作的目的是改变算法的局部搜索能力，有助于维持进化群体的多样性，防止过早陷入局部最优. 本文采用互换方式，即随机产生两个变异点，交换两点的基因值. 从种群中随机选择一个个体，对该个体的工序编码部分随机产生两个变异点，交换两点的基因值，同时将交换的基因位所对应的机器号也进行交换.

3 仿真实例分析

6 × 6(6 个工件，6 台机器) FJSP的加工工序，机器选择和加工时间矩阵表. 分别用标准遗传算法和本文提出的改进遗传算法对工件最小化最大完工时间进行优化计算，并分析优化计算结果.

遗传算法采用以下参数:种群规模为100，进化代数为100，交叉概率Pc = 0. 8，变异概率Pm =0. 1. 算法运行10 次，标准遗传算法的最大完工时间为20，收敛代数为75 代左右;改进遗传算法的最大完工时间为16，收敛代数为35 代左右. 改进遗传算法既缩短了工件完工时间，也加快了收敛代数. 从而验证了改进遗传算法的可行性

4 结论

传统遗传算法在进行种群初始化时采用的大多是随机选择方式，而本文提出了一种新的种群初始化方法，提高了种群初始解的质量. 最后对改进遗传算法进行了仿真实验，并将结果与标准遗传算法进行比较，结果表明了本算法的优越性和可行性.