5(396-402)基于OpenMP的并行遗传算法探讨_郑锋
心智与计算396心智与计算, Vol.1，No.4 (2007), 396-402
文章编号：MC - 2007-039
收稿日期：2007-08-10
出版日期：2007-12-30
? 2007 MC– 厦门大学信息与技术学院
基于OpenMP的并行遗传算法探讨
郑 锋，李名世，蔡佳佳
（厦门大学计算机科学系，福建厦门 361005）
zfxmu@https://www.sodocs.net/doc/c317542007.html,
摘要：目前主流CPU厂商都在致力发展多核处理器，增加芯片支持的并行能力，从而突破技术壁垒，提升运算速度。本文主要探讨近来流行的多核计算技术，介绍一种重要的工业标准OpenMP，以及对基于OpenMP的并行编程模式进行剖析。OpenMP编程主要是通过软件多线程来提升PC应用软件的功能和性能。随后以遗传算法求解TSP问题为例子实现了OpenMP多线程应用程序。
关键词：多核处理器；并行计算；多线程；OpenMP
中图分类号：TP301.6 文献标识码：A
Parallel Genetic Algorithms Based on OpenMP
ZHENG Feng, LI Ming-shi，CAI Jia-jia
(Department of Computer Science, Xiamen University, Xiamen 361005, China)
zfxmu@https://www.sodocs.net/doc/c317542007.html,
Abstract：The main CPU manufacturers are committing themselves to the development of multi-core processor,make a great progress in chip supporting parallel ability ,so breakthrough the technology bulwark and increasing the computation rate rapidly. The thesis probe into multi-core computation technology which is popular recently,introduce an important industrial standard OpenMP,and discuss the patterns for parallel programming based on OpenMP. Programmers add threads into codes to make full use of the new processor , that improves both function and performance of internet applications. And then realize the OpenMP multi-threading application for TSP based on genetic algorithm.
Key words：multi-core processor； parallel computation； multithreading ；OpenMP
1 前言
多核技术始终是近年来全球计算机技术发展的重要内容。自从英特尔在2006年底发布了全球第一
款主流服务器四核处理器后，英特尔一直致力于推动多核应用生态系统的成熟与发展。实际上，从2002年推出超线程技术开始，英特尔就开始了向多核技术转型的步伐。最终，英特尔公司将四个计算“大脑”装入一枚处理器中，随着至强5300的诞生，计算机行业宣告正式进入了多核时代。
多核计算将成为一种广泛普及的计算模式，影响企业和消费者用户的使用模式。如目前的服务器应用，要求高的吞吐率和在多处理器上的多线程应用；Internet的应用、P2P和普适计算的应用都促使了计算机性能的不断提升。大型企业的ERP、CRM等复杂应用，科学计算、政府的大型数据库管理系统、数字医疗领域、电信、金融等都需要高性能计算，多核技术可以满足这些应用的需求。
2 多线程与多核技术
2.1 并行计算平台
要实现软件并行执行的目标，就必须为多个线程同时执行提供一个硬件平台。一般而言，可以从两种不同的角度对计算机体系结构进行分类。第一种分类的依据是计算机在单个时间点能够处理的指令流数量。第二种分类的依据是计算在单个时间点上能够处理的数据流的数量。因此，任何给定的计算机系统都可以根据其处理指令和数据的方式来加以分类。这种分类方法就是从所周知的Flynn于1972年提出的Flynn分类法[1,2]。根据Flynn分类法，计算平台可以分为：单指令单数据流计算机（SISD）、多指令单数据流计算机（MISD）、单指令多数据流计算机（SIMD）、多指令多数据流计算机（MIMD）。
目前的计算机一般都属于SIMD机器或者MIMD机器，而这两种机器都提供了支持并行执行的硬件特性，因此软件开发人员能够非常方便地利用软件中存在的数据级和任务级并行性来提高程序性能。其中多指令多数据流计算机（MIMD）能够同时执行多个指令流，这些指令流分别对不同的数据流进行操作。这是目前最流行的并行计算平台。最新的多核计算平台[1]就属于MIMD范畴，例如Intel双核处理器。
2.2 多线程技术
随着软件技术的不断发展，应用程序也开始支持同时运行多个任务的功能。如今的服务器应用程序都是由多个线程或者多个进程组成，目前有好多方法可以对线程级的并行提供硬件或者软件上的支持。
一种方法是采用抢占式或时间片轮转的多任务操作系统。这种方法能够利用当前软件中日益增多的并发性。但是这种模式并不支持并行执行，因为在任何时间点上，CPU都是只执行一个指令流。
另一种方法就是增加计算机中物理处理器的数量，这样能够有效利用线程级并行性。多处理器系统支持真正意义上并行执行，因为多个线程或者进程能够在多个处理器上同时执行。不过这种方法会增加整个系统的造价。
实际的处理器是由大量不同的资源所组成的，包括体系结构状态——通用CPU寄存器、cache、总线、执行单元，以及分支预测逻辑等。通常我们定义一个线程，只需要体系结构状态信息即可。因此，通过复制这些体系结构状态信息的方法就能够创建多个逻辑处理器（或者线程）。然后，执行资源就被不同的逻辑处理器所共享。这就是大家熟悉的多线程技术（SMT），也叫超线程技术（HT）。
2.3 多核技术
在多线程技术之后出现了多核处理器。多内核是指在一枚处理器芯片中集成两个或者多个完整的计算内核。多核处理器采用单芯片多处理器（CMP）的设计技术[1]。单芯片多处理器通过在一个芯片上集成多个微处理器核心来提高程序的并行性。每个微处理器核心实质上都是一个相对简单的单线程微处理器或者比较简单的多线程微处理器，这样多个微处理器核心就可以并行地执行程序代码，因而具有了较高的线程级并行性。
单核处理器只能够将多个指令流交错执行，并不能真正将它们同时执行，这样，单核结构上的多线程应用程序的性能就受到了限制。单核平台的这种性能瓶颈在多核体系结构中就不存在了。多核平台为开发人员提供了一种优化应用程序的渠道，那就是通过仔细分配加载到各线程（处理器核）上工作负载就能够得到性能上有提升。并且，开发人员也可以对应用程序的代码加以优化，使其能够更加充分地使用多个处理器资源，进而达到提升应用程序性能的目的。
3 OpenMP并行编程模型
3.1 OpenMP简介
OpenMP[3]起源于ANSI X3H5标准，它具有简单、移植性好和可扩展等优点，是共享存储系统编程的一个工业标准。OpenMP是一个为在共享存储的多处理机[4,5]上编写并行程序而设计的应用编程接口，用于编写可移植的多线程应用程序。OpenMP程序编程模型包括一组与平台无关的编译指导（pragmas）、制导命令（directive）、函数调用和环境变量，可以显式地指导编译器如何以及何时利用应用程序中的并行性。OpenMP是通过与标准Fortran，C和C++结合进行工作的，对于同步共享变量、合理分配负载等任务，都提供了有效的支持，具有简单通用，开发快速的特点。
3.2 OpenMP并行编程模型
首先，OpenMP是基于线程的并行编程模型(Programming Model)，一个共享存储的进程由多个线程组成，OpenMP就是基于已有线程的共享编程范例；其次，OpenMP是一个外部的编程模型，而不是自动编程模型，它能够使程序员完全控制并行化。
OpenMP使用Fork-Join并行执行模型[2]。当程序开始执行的时候只有一个叫做主线程存在，如图1所示。主线程会一直串行的执行，直到遇见第一个并行域(Parallel Region)才开始并行执行。当遇到需要进行并行运算时，主线程创建一队并行的线程，并行域中的代码在不同的线程队中并行执行；当派生出的线程在并行域中执行完之后，它们退出或者挂起，最后只有主线程在执行。实际上，所有OpenMP的并行化，都是通过使用嵌入到C/C++或Fortran源代码中的编译制导语句来达到的。并且，一个OpenMP 应用编程接口(API)的并行结构可以嵌入到别的并行结构中去。应用编程接口还可以随着不同并行域的需要动态地改变线程数。
图1 fork/join 并行模式
Fig.1 fork/join parallel pattern
可以将顺序执行的程序看作是共享存储模型程序的一种特殊情况，即没有fork/join 的形式。无论是仅仅在一个循环并行执行中使用了一个fork/join 的并行程序，还是那些大部分代码段都被并行执行的程序，它们都属于共享存储的并行程序。因此，共享存储模型支持增量并行化，就是说可以一次并行化程序中的一段代码，然后继续进行多次这样的操作，从而可以将整个顺序程序转化为并行程序。
3.3 OpenMP 循环调度与分块
在多线程程序中，要实现较好的负载平衡而获取最优的性能，就必须对循环进行高效的调度与分块。这样才能保证执行核尽可能地在大部分时间内保持忙碌状态，同时将调度开销、上下文切换开销和同步开销降到最低。如果负载平衡做得很差，那么某些线程可能很早就完成了自己的工作，从而导致处理器资源闲置，损失了性能。为了提供一种简单的方法以便能够在多个处理核之间调节工作负载，OpenMP 有四种调度方案[3]，可以适用于很多情况：static 、dynamic 、guided 和runtime 。在OpenMP for 结构中，使用schedule 子句将循环调度和分块信息传能编译器与运行时库。
（1）静态平衡调度策略
默认情况下，OpenMP parallel for 循环或任务分配for 循环都是采用这种调度策略。这种调度是将循环的迭代以近乎平均的方式分布到各个线程上。如果有m 次迭代，线程组中有N 个线程，那么每个线程就执行m/N 次迭代。使用静态调度策略，能够尽可能地降低当多个处理器同时访问同一片内存区域时发生访存冲突的几率。这种方案之所以可行，是因为循环一般是顺序访存的，所以将循环分割为较大的块就可以减少重叠访存的几率，提高处理器cache 的使用效率。
（2）动态调度策略
主线程
其他线程
时
间
fork
join
join fork
块是以先来先服务的方式进行处理的，默认的块大小是1。每次迭代的次数和schedule 子句中所指定的块大小相等，但最后一个块例外。当一个线程执行完分配给它的迭代后，它将请求另一组迭代，其数量由块大小指定。这个过程不断重复，直至所有的迭代都完成。最后一组迭代的个数可能小于块大小。
（3）指导策略
一个循环的划分是基于下列公式来完成的，其中初值0β=迭代数。??????=N k k 2βπ其中N 是线程个数，k π代表第k 块的大小，从第0块开始，在计算第k 块的大小时，k β代表剩下的未调度的循环迭代次数。
如果k π的值太小，那么该值就会被块大小S 所取代，S 是由schedule(guided, chunk-size)子句指定的。因此，对于guided 调度策略来说，循环分块的方法取决于线程个数，迭代次数和块大小。Intel C++和Fortran 编译器所支持的guided 调度策略是遵从OpenMP2.5标准来实现的。
（4）运行时调度策略
如果在schedule 子句中指定runtime 作为调度策略，OpenMP 运行时环境就对当前的for 循环使用由OMP_SCHEDULE 环境变量所指定的调度方案。
3.4 OpenMP 并行优化技术
OpenMP 并行化一般针对循环级的细粒度的并行化，这主要是因为：绝大多数的主要计算量都是集中在循环中，对循环的并行化把握住了问题的关键；细粒度的并行化的性能较好，并且工作量小，程序员几乎不用关心其他并行化细节，而只在要循环计算外使用OpenMP 编译制导指令即可。
OpenMP 并行化的循环选取是个很重要的问题，可以遵循以下几个原则：
（1）尽量选择计算时间占全局计算时间比例大的循环进行并行化，因为对循环的并行化同时也带来进程和线程的反复切换调度的开销，这对于计算量不大的循环来说是不值得的。
（2）可能有一些循环因为存在数据相关性而无法并行化。如果这个循环计算量很小，可能对程序的性能影响不大；但如果这个循环的计算量很大，不对它并行化可能使程序性能损失很多时，则可以考虑进行循环变换，使其能够并行化，从而优化这样的循环计算。
在进行性能优化时，必须在优化内存利用和优化负载平衡之间进行折中，因为有利于负载平衡的策略也有可能对访存的性能不利。在调整块大小时可能会对性能带来负面的影响。随着块大小的减小，线程用于从任务队列中获得任务的时间会增加，结果使访问任务队列的开销增加，从而降低性能，有可能抵消负载平均带来的性能提升。
4 遗传算法解决TSP 问题的OpenMP 并行实现
遗传算法[6]是一种模拟生物在自然环境中的遗传和进化过程而形成的概率搜索算法，它模仿生物要自然环境中的遗传和进化机理，反复将选择算子、交叉算子和变异算子作用于种群。最终可得到问题的最优解或近似最优解。
4.1 多核处理器上的并行遗传算法
并行遗传算法就是对评价、选择、交叉、变异这四个环节进行改进：
(1)群体中各个个体适应度的评价在遗传算法执行时间中占用较大，但相互间又无依赖关系，这样的个体适应度评价计算就可以相互独立、相互并行的在多核处理器不同的核上同时进行。
(2)从父代群体进行选择、交叉、变异等遗传操作产生子代群体的过程可以独立并发地在多核处理器不同的核上同时进行。
(3)群体中的单个或者一组个体的进化过程可以相互独立地进行，将群体分为子群体，分而治之，各自进化若干代以后相互交换信息。
4.2 OpenMP并行实现
根据上面的改进提要，如图2所示，是基于遗传算法解决TSP问题的OpenMP并行实现。主界面包含四个部分：左边是绘制TSP路径坐标图，右边是参数选择区域，右下角是一些功能选择，最下面的根据参数得出的实验结果数据区域。
该实验完成了求解TSP问题，并得出最佳路径和所用的求解时间。可以根据多核（具体核的个数）来选择参数，子群的个数，有利于效率的提高。还有子群的规模也是影响计算效率的一个重要因素。
图2 OpenMP示例程序
Fig.2 OpenMP programme
5 结束语
从目前来看，多核处理器的推广还受到一定程度的限制，如一些桌面应用尚不支持多线程、多核处理器价格相对偏高、应用开发工具不成熟等。随着应用需求的扩大和技术的不断进步，多核必将展示出其强大的性能优势。多核处理器是处理器发展的必然趋势，无论是移动与嵌入式应用、桌面应用还是服务器应用，都将采用多核的架构，因此多核技术应用前景广阔。本文对基于这种多核微机的编程模式进行了分析和探讨。用基于OpenMP工具实现了求解TSP问题。计算机世界正进入多核处理器时代，OpenMP将成为程序员必不可少的工具。
参考文献：
[1] Shameem Akhter, Jason Roberts.多核程序设计技术[M]. 李宝峰,等译.北京：电子工业出版社, 2007.
[2] Barry Willkinson , Michael Allen.并行程序设计 [M]. 陆鑫达,等译. 2版.北京：机械工业出版社,2005.
[3] Miachael J Quinn. Parallel programming in C with MPI and OpenMP[M]. 北京：清华大学出版社, 2004.
[4] Timothy G Mattson,Beverly A Sanders,Berna L Massingill.并行编程模式[M]敖富江,译.北京：清华大学出版社,2005.
[5] 陈国良.并行算法实践[M].北京：高等教育出版社,2004.
[6] 刘勇,康立山,陈毓屏.非数值并行算法:第二册遗传算法[M].北京：科学出版社,2000.
作者简介：
郑锋（1983-），男，硕士研究生，研究方向：并行计算，多核计算。
遗传算法并行化的研究.doc
遗传算法并行化的研究 学号：SC02011036 姓名：黄鑫 摘要 本文是针对遗传算法并行化进行了研究，首先简要给出了基本遗传算法的形式化描述，然后做了并行性的分析，详细介绍了遗传算法的结构化并行模型：步进模型，岛屿模型，邻接模型，最后指出了进一步要研究的课题。 关键词：遗传算法，并行计算，结构化GA 1引言 遗传算法（GA）是根据达尔文进化论“优胜劣汰，适者生存”的一种启发式搜索算法。采用选择，交叉，变异等基本变化算子在解空间同时进行多点搜索，本身固有并行性。随着大规模并行机的迅速发展，将并行机的高速性与遗传算法并行性结合起来，从而促进遗传算法的发展。然而，仅仅将基本遗传算法硬件并行化伴随着大量通讯开销等问题，从而必须对标准GA的进行改进，使得并行遗传算法不单单是遗传算法硬件并行实现，更重要的是结构化的遗传算法。本文首先给出了GA形式化描述，对基本GA的可并行性做出分析，然后给出了并行GA的模型，最后指出了并行遗传算法还需要解决的问题。 2 基本遗传算法 在这里我们不对遗传算法做过多的介绍，只是给出基本遗传算法的形式化描述：begin (1)initialization (1.1)产生一个初始群体 (1.2)评估第一代整个群体的适应度值 （2）while running do (2.1)选择父代 (2.2)交叉操作 (2.3)子代变异 (2.4)评估子代的适应度 (2.5)子代取代父代，形成新的一带个体 endwhile end 3 遗传算法的并行性分析 从第一节对遗传算法的描述，我们可以看出基本遗传算法模型是一个反复迭代的进化计算过程，通过对一组表示候选解的个体进行评价、选择、交叉、变异等操作，来产生新一代的个体(候选解)，这个迭代过程直到满足某种结束条件为止。对应于基本遗传算法的运行过程，为实现其并行化要求，可以从下面四种并行性方面着手对其进行改进和发展。 并行性Ⅰ：个体适应度评价的并行性。 个体适应度的评价在遗传算法中占用的运行时间比较大。通过对适应度并行计算方法的研究，可提高个体适应度评价的计算效率。 并行性Ⅱ：整个群体各个个体适应度评价的并行性。
遗传算法与优化问题
实验十遗传算法与优化问题 一、问题背景与实验目的 遗传算法(Genetic Algorithm —GA),就是模拟达尔文的遗传选择与自然淘汰的生物进化过程的计算模型，它就是由美国Michigan大学的J、Holla nd教授于1975 年首先提出的?遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位. 本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题,使读者能够学会利用遗传算法进行初步的优化计算? 1. 遗传算法的基本原理 遗传算法的基本思想正就是基于模仿生物界遗传学的遗传过程?它把问题的参数用基因代表，把问题的解用染色体代表(在计算机里用二进制码表示),从而得到一个由具有不同染色体的个体组成的群体?这个群体在问题特定的环境里生存 竞争,适者有最好的机会生存与产生后代?后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环境，不断进化,最后收敛到一族最适应环境的类似个体，即得到问题最优的解?值得注意的一点就是，现在的遗传算法就是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身就是否完全正确并不重要(目前生物界对此学说尚有争议). (1)遗传算法中的生物遗传学概念 由于遗传算法就是由进化论与遗传学机理而产生的直接搜索优化方法；故而 在这个算法中要用到各种进化与遗传学的概念? 首先给出遗传学概念、遗传算法概念与相应的数学概念三者之间的对应关系这些概念
（2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）:选择（Selection）、交叉（Crossover）、变异（Mutation）. 遗传算法基本步骤主要就是：先把问题的解表示成“染色体”，在算法中也就就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就就是假设的可行解.然后，把这些假设的可行解置于问题的“环境”中,并按适者生存的原则从中选 择出较适应环境的“染色体”进行复制 ，再通过交叉、变异过程产生更适 应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就就是问题的最优解. 下面给出遗传算法的具体步骤，流程图参见图1: 第一步:选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步:定义适应函数，便于计算适应值； 第三步:确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数； 第四步:随机产生初始化群体； 第五步:计算群体中的个体或染色体解码后的适应值； 第六步:按照遗传策略，运用选择、交叉与变异算子作用于群体，形成下一代群体； 第七步:判断群体性能就是否满足某一指标、或者就是否已完成预定的迭代次数,不满足则返回第五步、或者修改遗传策略再返回第六步. 图1 一个遗传算法的具体步骤
智能信息处理导论简答题
1、简述可拓思想及其拓展工具 可拓思想是利用物元理论、事元理论和可拓集合理论，结合各应用理论和方法去处理该领域中的矛盾问题，以化不可行为可行，不可知为可知，化不属于为属于、化对立为共存。 可拓拓展工具定性工具物元和事元是可拓学的基本概念，可拓变换是解决矛盾问题的基本工具，可拓分析方法是寻求可拓变换的依据。利用它们可以从定性的角度分析事物开拓的可能性。 定量工具可拓集合是描述事物具有某种性质的程度和量变与质变的定量化工具。 2、什么是云计算？云计算为什么备受关注？为什么要实现云计算？ 云计算的基本原理是通过使计算分布在大量的分布式计算机上，而非本地计算机或远程服务中，企业数据中心的运行将更与互联网相似。这使得企业能够将资源切换到需要的应用上，根据需求访问计算机和存储系统 云计算是一种革命性的举措，打个比方，这就好比是从古老的单台发电机模式转向了电厂集中供电的模式。它意味着计算能力也可以作为一种商品进行流通。它最大的不同在于它是通过互联网进行传输的。 在未来只需一台笔记本或者手机，就可以通过网络服务来满足人们一切甚至包括超级计算这样的任务。最终用户才是云计算的真正拥有者。云计算的思想：把力量联合起来，给其中的每一个成员使用。 3、简述粗集理论. ①利用抽象代数来研究粗糙集代数空间这种特殊的代数结构。②利用拓扑学描述粗糙空间。 ③还有就是研究粗糙集理论和其他软计算方法或者人工智能的方法相接合，例如和模糊理论、神经网络、支持向量机、遗传算法等。④针对经典粗糙集理论框架的局限性，拓宽粗糙集理论的框架，将建立在等价关系的经典粗糙集理论拓展到相似关系甚至一般关系上的粗糙集理论 4、比较协同进化遗传算法与普通遗传算法。 遗传算法虽然实现简单，操作方便，但是存在很多的缺陷：①很容易导致“早熟”，陷入局部最优；②随着问题规模的增大，其计算复杂度明显增加，收敛性显著降低，搜索问题空间能力也下降；③依靠简单的交叉、变异操作，很容易产生不可行解；④交叉产生的子代可能一个适应度很高，另一个很低，低的个体虽然含有较好的基因，但是会被淘汰。 两种算法的比较结果很明显就可以看出两种算法的优劣：CGA、要明显优于GA，计算是时间短，收敛速度快，而且收敛精度也比较高。在求解分类神经网络训练问题计算工作量大大减少，同样达到90%的分类精度，CGA的遗传代数只有GA的1/3.在求解Manipulator Path Planning问题CGA占用CPU的时间只有GA的1/9 5、比较免疫算法与遗传算法。 (1)免疫算法与遗传算法起源于抗原与抗体之间的内部竞争，其相互作用的环境既包括外部也包括内部的环境；而遗传算法起源于个体与自私基因之间的外部竞争。(2)免疫算假设免疫元素互相作用，即每一个免疫细胞等个体可以相互作用，而遗传算法不考虑个体之间的作用。(3)免疫算法中，基因可以由个体自己选择，而在遗传算法中基因有环境选择。(4)免疫算法中，基因组合是为了获得多样性，一般不用交叉算子，因为免疫算法中基因是在同一代个体进行进化，这种情况下设交叉概率为0；而遗传算法后代个体基因通常是由父代交叉的结果，交叉用于混合基因(5)免疫算法选择个变异阶段明显不同，而遗传算法中它们是交替进行的。 6、请描述遗传算法特点。 (1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传
智能算法实验报告
人工智能实验—智能算法 实验一蚂蚁算法 一、实验目的： 理解蚂蚁算法的本质，会编写蚂蚁算法来求解TSP问题。 二、实验原理： 蚂蚁在寻找食物源时，能在其走过的路上释放一种特殊的分泌物——信息素(随着时间的推移该物质会逐渐挥发), 后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度。 而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制, 通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。 三、实验内容： #include
遗传算法概述
第1期作者简介：李红梅（1978-），女，湖南湘潭人，硕士，广东白云学院讲师，研究方向为演化计算。 1遗传算法的发展史 遗传算法（Genetic Algorithms ）研究的历史比较短，20世纪 60年代末期到70年代初期，主要由美国家Michigan 大学的John Holland 与其同事、学生们研究形成了一个较完整的理论 和方法，遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。我国对于GA 的研究起步较晚，不过从20世纪90年代以来一直处于不断上升中。 2遗传算法的基本思想 遗传算法是从代表问题可能潜在解集的一个种群（popu- lation ）开始的，而一个种群则由经过基因（gene ）编码（coding ） 的一定数目的个体（individual ）组成。每个个体实际上是染色体（chromosome ）带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其内部表现是某种基因组合，它决定了个体的形状的外部表现。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation ）演化产生出越来越好的近似解。在每一代中，根据问题域中个体的适应度（fitness ）、大小挑选（selection ）个体，借助于自然遗传学的遗传算子（genetic operators ）进行组合交叉（crossover ）和变异（mutation ），产生出代 表新的解集的种群。这个过程将导致后生代种群比前代更加适应环境，末代种群中的最优个体经过解码（decoding ），可以作为问题近似最优解。 3遗传算法的一般流程 （1）随机产生一定数目的初始种群，每个个体表示为染色 体的基因编码； （2）计算每个个体的适应度，并判断是否符合优化准则。若符合，输出最佳个体及其代表的最优解并结束计算，否则转向第3步； （3）依据适应度选择再生个体，适应度高的个体被选中的概率高，适应度低的个体可能被淘汰； （4）执行交叉和变异操作，生成新的个体；（5）得到新一代的种群，返回到第2步。 4遗传算法的特点 传统的优化方法主要有三种：枚举法、启发式算法和搜索 算法： （1）枚举法 可行解集合内的所有可行解，以求出精确最 优解。对于连续函数，该方法要求先对其进行离散化处理，这样就可能因离散处理而永远达不到最优解。此外，当枚举空间比较大时，该方法的求解效率比较低，有时甚至在目前先进计算机工具上无法求解。 （2）启发式算法 寻求一种能产生可行解的启发式规则， 以找到一个最优解或近似最优解。该方法的求解效率比较高，但对每一个需求解的问题必须找出其特有的启发式规则。这个启发式规则一般无通用性，不适合于其它问题。 （3）搜索算法 寻求一种搜索算法，该算法在可行解集合 的一个子集内进行搜索操作，以找到问题的最优解或者近似最优解。该方法虽然保证不了一定能够得到问题的最优解，但若适当地利用一些启发知识，就可在近似解的质量和效率上达到一种较好的平衡。 遗传算法不同于传统的搜索和优化方法。主要区别在于： ①遗传算法直接处理问题参数的适当编码而不是处理参数集 本身。②遗传算法按并行方式搜索一个种群数目的点，而不是 遗传算法概述 李红梅 （广东白云学院计算机系，广东广州510450） 摘要：遗传算法是一种全局优化的随机搜索算法。它是解决复杂优化问题的有力工具。在工程设计、演化硬件电路 设计以及人工智能等方面应用前景广阔。系统地介绍了遗传算法的发展史、基本思想、特点、主要应用领域等相关方 面。 关键词：遗传算法；搜索；进化；最优解；种群中图分类号：TP312 文献标识码：A 文章编号：1672-7800（2009）01-0067-02 第8卷第1期2009年1月 Vol.8No.1Jan.2009 软件导刊 Software Guide
自适应PID控制综述(完整版)
自适应PID控制 摘要：自适应PID控制是一门发展得十分活跃控制理论与技术,是自适应控制理论的一个重要组成部分,本文简要回顾PID控制器的发展历程,对自适应PID控制的主要分支进行归类,介绍和评述了一些有代表性的算法。 关键词：PID控制，自适应，模糊控制，遗传算法。 Abstract: The adaptive PID control is a very active developed control theory and technology and is an important part of adaptive control theory.This paper briefly reviews the development process PID controller.For adaptive PID control of the main branches, the paper classifies,introduces and reviews some representative algorithms. Keywords: PID control, adaptive, fuzzy control, genetic algorithm 1 引言 从问世至今已历经半个世纪的PID控制器广泛地应用于冶金、机械、化工、热工、轻工、电化等工业过程控制之中，PID控制也是迄今为止最通用的控制方法， PID控制是最早发展起来的控制策略之一，因为他所涉及的设计算法和控制结构都很简单，并且十分适用于工程应用背景，所以工业界实际应用中PID 控制器是应用最广泛的一种控制策略(至今在全世界过程控制中用的80% 以上仍是纯PID调节器，若改进型包含在内则超过90%)。由于实际工业生产过程往往具有非线性和时变不确定性，应用常规PID控制器不能达到理想控制效果，长期以来人们一直寻求PID控制器参数的自动整定技术，以适应复杂的工况和高指标的控制要求。随着微机处理技术和现代控制理论诸如自适应控制、最优控制、预测控制、鲁棒控制、智能控制等控制策略引入到PID控制中，出现了许多新型PID控制器。人们把专家系统、模糊控制、神经网络等理论整合到PID控制器中，这样既保持了PID控制器的结构简单、适用性强和整定方便等优点，又通过先进控制技术在线调整PID控制器的参数，以适应被控对象特性的变化。 2 自适应PID控制概念及发展 2.1 PID控制器 常规PID控制系统原理框图如下图所示，系统由模拟PID控制器和被控对象组成。
遗传算法的基本原理
第二章 遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S 作为搜索空间，f ：S —>R 为目标函数，全局优化问题作为任务)(max x f S x ∈给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值+∞<=)(**x f f 称为一个全局最大值，当且仅当x ? S x ∈，(ρi i b a <，i 12）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P ； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。
2.1.3 遗传编码 由于GA 计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA 个体的表现型集合做组成的空间称为问题（参数）空间，由GA 基因型个体所组成的空间称为GA 编码空间。遗传算子在GA 编码空间中对位串个体进行操作。 定义：由问题空间向GA 编码空间的映射称为编码，而有编码空间向问题空间的映射成为译码。 1）2）3）它们对1） 2） k =1,2,…,K; l =1,2,…,L; K=2L 其中，个体的向量表示为),,,(21kL k k k a a a a =，其字符串形式为kL k k k a a a s 21=，s k 称为个体a k 对应的位串。表示精度为)12/()(--=?L u v x 。 将个体又位串空间转换到问题空间的译码函数],[}1,0{:v u L →Γ的公式定义为： 对于n 维连续函数),,2,1](,[),,,,(),(21n i v u x x x x x x f i i i n =∈=，各维变量的二进制
并行遗传算法
并行遗传算法及其应用 1、遗传算法（GA）概述 GA是一类基于自然选择和遗传学原理的有效搜索方法，它从一个种群开始，利用选择、交叉、变异等遗传算子对种群进行不断进化，最后得到全局最优解。生物遗传物质的主要载体是染色体，在GA中同样将问题的求解表示成“染色体Chromosome”，通常是二进制字符串表示，其本身不一定是解。首先，随机产生一定数据的初始染色体，这些随机产生的染色体组成一个种群（Population），种群中染色体的数目称为种群的大小或者种群规模。第二：用适值度函数来评价每一个染色体的优劣，即染色体对环境的适应程度，用来作为以后遗传操作的依据。第三：进行选择（Selection），选择过程的目的是为了从当前种群中选出优良的染色体，通过选择过程，产生一个新的种群。第四：对这个新的种群进行交叉操作，变异操作。交叉、变异操作的目的是挖掘种群中个体的多样性，避免有可能陷入局部解。经过上述运算产生的染色体称为后代。最后，对新的种群（即后代）重复进行选择、交叉和变异操作，经过给定次数的迭代处理以后，把最好的染色体作为优化问题的最优解。 GA通常包含5个基本要素：1、参数编码：GA是采用问题参数的编码集进行工作的，而不是采用问题参数本身，通常选择二进制编码。2、初始种群设定：GA随机产生一个由N个染色体组成的初始种群（Population），也可根据一定的限制条件来产生。种群规模是指种群中所含染色体的数目。3、适值度函数的设定：适值度函数是用来区分种群中个体好坏的标准，是进行选择的唯一依据。目前主要通过目标函数映射成适值度函数。4、遗传操作设计：遗传算子是模拟生物基因遗传的操作，遗传操作的任务是对种群的个体按照它们对环境的适应的程度施加一定的算子，从而实现优胜劣汰的进化过程。遗传基本算子包括：选择算子，交叉算子，变异算子和其他高级遗传算子。5、控制参数设定：在GA的应用中，要首先给定一组控制参数：种群规模，杂交率，变异率，进化代数等。 GA的优点是擅长全局搜索，一般来说，对于中小规模的应用问题，能够在许可的范围内获得满意解，对于大规模或超大规模的多变量求解任务则性能较差。另外，GA本身不要求对优化问题的性质做一些深入的数学分析，从而对那些不
第五章-遗传算法工具箱函数
第五章遗传算法工具箱函数 本章介绍英国设菲尔德大学开发的遗传算法工具箱函数。 由于MATLAB高级语言的通用性，对问题用M文件编码，与此配对的是MA TLAB先进的数据分析、可视化工具、特殊目的的应用领域工具箱和展现给使用者具有研究遗传算法可能性的一致环境。MATLAB遗传算法工具箱为遗传算法从业者和第一次实验遗传算法的人提供了广泛多样的有用函数。 遗传算法工具箱使用MA TLAB矩阵函数为实现广泛领域的遗传算法建立一套通用工具，这个遗传算法工具是用M文件写成的，是命令行形式的函数，能完成遗传算法大部分重要功能的程序的集合。用户可通过这些命令行函数，根据实际分析的需要，编写出功能强大的MATLAB程序。 5.1 工具箱结构 本节给出GA工具箱的主要程序。表5.1为遗传算法工具箱中的各种函数分类表。 表5.1 遗传算法工具箱中函数分类表
5.1.1 种群表示和初始化 种群表示和初始化函数有：crtbase，crtbp，crtrp。 GA工具箱支持二进制、整数和浮点数的基因表示。二进制和整数种群可以使用工具箱中的crtbp建立二进制种群。crtbase是附加的功能，它提供向量描述整数表示。种群的实值可用crtrp进行初始化。在二进制代码和实值之间的变换可使用函数bs2rv，它支持格雷码和对数编码。 5.1.2 适应度计算 适应度函数有：ranking，scaling。 适应度函数用于转换目标函数值，给每一个个体一个非负的价值数。这个工具箱支持Goldberg的偏移法(offsetting)和比率法以及贝克的线性评估算法。另外，ranking函数支持非线性评估。 5.1.3 选择函数 选择函数有：reins，rws，select，sus。 这些函数根据个体的适应度大小在已知种群中选择一定数量的个体，对它的索引返回一个列向量。现在最合适的是轮盘赌选择(即rws函数)和随机遍历抽样(即sus函数)。高级入口函数select为选择程序，特别为多种群的使用提供了一个方便的接口界面。在这种情况下，代沟是必须的，这就是整个种群在每一代中没有被完全复制，reins能使用均匀的随机数或基于适应度的重新插入。 5.1.4 交叉算子 交叉算子函数有：recdis，recint，reclin，recmut，recombin，xovdp，xovdprs，xovmp，xovsh，xovshrs，xovsp，xovsprs。 交叉是通过给定的概率重组一对个体产生后代。单点交叉、两点交叉和洗牌交叉是由xovsp、xovdp、xovsh函数分别完成的。缩小代理交叉函数分别是：xovdprs、xovshrs和xovsprs。通用的多点交叉函数是xovmp，它提供均匀交换的支持。为支持染色体实值表示，离散的、中间的和线性重组分别由函数recdis、recint、reclin完成。函数recmut提供具有突变特征的线性重组。函数recombin是一高级入口函数，对所有交叉操作提供多子群支持入口。 5.1.5 变异算子 变异算子函数有：mut，mutate，mutbga。
遗传算法的并行实现
遗 传 算 法 （基于遗传算法求函数最大值） 指导老师：刘建丽 学号：S201007156 姓名：杨平 班级：研10级1班
遗传算法 一、 遗传算法的基本描述 遗传算法（Genetic Algorithm ，GA ）是通过模拟自然界生物进化过程来求解优化问题的一类自组织、自适应的人工智能技术。它主要基于达尔文的自然进化论和孟德尔的遗传变异理论。多数遗传算法的应用是处理一个由许多个体组成的群体，其中每个个体表示问题的一个潜在解。对个体存在一个评估函数来评判其对环境的适应度。为反映适者生存的思想，算法中设计一个选择机制，使得：适应度好的个体有更多的机会生存。在种群的进化过程中，主要存在两种类型的遗传算子：杂交和变异。这些算子作用于个体对应的染色体，产生新的染色体，从而构成下一代种群中的个体。该过程不断进行，直到找到满足精度要求的解，或者达到设定的进化代数。显然，这样的思想适合于现实世界中的一大类问题，因而具有广泛的应用价值。遗传算法的每一次进化过程中的，各个体之间的操作大多可以并列进行，因此，一个非常自然的想法就是将遗传算法并行化，以提高计算速度。本报告中试图得到一个并行遗传算法的框架，并考察并行化之后的一些特性。为简单起见（本来应该考虑更复杂的问题，如TSP 。因时间有些紧张，做如TSP 等复杂问题怕时间不够，做不出来，请老师原谅），考虑的具有问题是：对给定的正整数n 、n 元函数f ，以及定义域D ，求函数f 在D 内的最大值。 二、 串行遗传算法 1． 染色体与适应度函数 对函数优化问题，一个潜在的解就是定义域D 中的一个点011(,,...,)n x x x -，因此，我们只需用一个长度为n 的实数数组来表示一个个体的染色体。由于问题中要求求函数f 的最大值，我们可以以个体所代表点011(,,...,)n x x x -在f 函数下的值来判断该个体的好坏。因此，我们直接用函数f 作为个体的适应度函数。 2． 选择机制 选择是遗传算法中最主要的机制，也是影响遗传算法性能最主要的因素。若选择过程中适应度好的个体生存的概率过大，会造成几个较好的可行解迅速占据种群，从而收敛于局部最优解；反之，若适应度对生存概率的影响过小，则会使算法呈现出纯粹的随机徘徊行为，算法无法收敛。下面我们介绍在实验中所使用的选择机制。
谈谈遗传算法的原理
谈谈遗传算法的原理 发表时间：2011-08-24T09:52:45.450Z 来源：《魅力中国》2011年7月上供稿作者：朱小宝 [导读] 从上表中可以看出，群体经过一代进化之后，其适应度的最大值、平均值都得到了明显的改进。 朱小宝 (南昌航空大学飞行器工程学院江西南昌 330029) 中图分类号：TP301.6 文献标识码：A 文章编号：1673-0992（2011）07-0000-01摘要：自从霍兰德于1975年在他的著作《Adaption im Natural and artificial Systems》中首次提出遗传算法以来，经过了近30年的研究，现在已经发展到了一个比较成熟的阶段，并且在实际中得到了很好的应用。为了更好的了解遗传算法，本文通过最简单的一个手工计算实例来还原遗传算法的全过程。 关键词：遗传算法生物进化染色体种群 自然界的生物进化是按“适者生存，优胜劣汰”规律进行的，而遗传算法就是模拟达尔文的自然选择学说和自然界的生物进化过程的一种计算模型。其基本思想是力求充分模仿这一自然寻优过程的随机性、鲁棒性和全局性，这是一种全局优化搜索算法，因为其直接对结构对象进行操作，不存在求导和函数连续性的限定。 遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法的操作对象是一群二进制串(称为染色体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适应值比例的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止。 遗传算法主要步骤： （1）编码：由于遗传算法不能直接处理解空间的数据，必须通过编码将它们表示成遗传空间的基因型串结构数据。 （2）选择初始种群：随机产生N个初始串结构数据，每个串结构数据称为一个个体，也称为染色体，N个个体体构成了一个种群。 （3）选择适应度函数：遗传算法在搜索过程中一般不需要其他外部信息或知识，仅用适应度函数来评价个体的适应度。 （4）选择：利用选择概率再随机的选择个体和复制数量。选择算子的设计可依据达尔文适者生存的进化论原则，选择概率大的被选中的机会较多。 （5）杂交：对被选中的个体进行随机配对并随机的选择基因交换位，交换基因后产生新的个体，全体新个体构成新的（下一代）种群。 （6）变异：变异操作是按位进行求反，对二二进制编码的个体而言，就是对随机选中的某位进行求反运算，即“0”变“1”，“1”变大“0”。 （7）一代种群通过遗传，即选择、杂交和变异产生下一代种群。新种群又可重复上述的选择、杂交和变异的遗传过程。 为更好地理解遗传算法的运算过程，下面用手工计算来简单地模拟遗传算法的各个主要执行步骤。 求下述二元函数的最大值： Max f(x1,x2)= x12+ x22 S,t, x1∈{1,2,3,4,5,6,7} x2∈{1,2,3,4,5,6,7} (1) 个体编码 遗传算法的运算对象是表示个体的符号串，所以必须把变量 x1, x2 编码为一种符号串。本题中，用无符号二进制整数来表示。因 x1, x2 为 0 ~ 7之间的整数，所以分别用3位无符号二进制整数来表示，将它们连接在一起所组成的6位无符号二进制数就形成了个体的基因型，表示一个可行解。例如，基因型 X＝101110 所对应的表现型是：x＝[5，6]。个体的表现型x和基因型X之间可通过编码和解码程序相互转换。 (2) 初始群体的产生 群体规模的大小取为4，即群体由4个个体组成，每个个体可通过随机方法产生。 如：011101，101011，011100，111001 (3) 适应度汁算 目标函数总取非负值，并且是以求函数最大值为优化目标，故可直接用目标函数值作为个体的适应度。 (4) 选择运算 我们采用与适应度成正比的概率来确定各个个体复制到下一代群体中的数量。其具体操作过程是： 1.先计算出群体中所有个体的适应度的总和 fi ( i=1.2,…,M )； 2.fi其次计算出每个个体的相对适应度的大小 fi / ，它即为每个个体被遗传到下一代群体中的概率， 3.每个概率值组成一个区域，全部概率值之和为1； 4.最后再产生一个0到1之间的随机数，依据该随机数出现在上述哪一个概率区域内来确定各个个体被选中的次数。
MapReduce求解物流配送单源最短路径研究
MapReduce求解物流配送单源最短路径研究 摘要: 针对物流配送路线优化，提出了将配送路线问题分解成若干可并行操作的子问题的云计算模式。详细论述了基于标色法的MapReduce广度优先算法并行化模型、节点数据结构、算法流程和伪代码程序，并通过将该算法应用于快递公司的实际配送，验证了该算法的可行性。关键词: 物流配送； MapReduce；并行计算；最短路径 随着电子商务的普及，人们网上购物的习惯逐渐形成。截止2012年11月30日，阿里巴巴集团旗下淘宝和天猫2012年总交易额已经突破一万亿。综合淘宝和天猫的交易数据来看，以快递员为主体的中国物流配送业对电子商务发展的促进起到了巨大作用。同时传统邮政担负的包裹配送业务比重也逐渐地倾斜于第三方物流配送公司。目前我国物流配送运输成本占整个物流成本的35%~50%左右[1]。由于网购物品用户分布在城市的不同地方,为了控制配送运输成本，改善配送秩序，需要优化配送路线。优化配送路线的求解有串行算法和并行算法。串行算法主要表现在基于算法本身以及其优化组合的方法,例如CLARK G和WRIGHT J的节约算法、GILLETT B E和MILLER L R的扫描算法、Christofides等人的k度中心树和相关算法、Gendrean的禁忌搜索方法、LAWRENCE J 的遗传算法、Dijkstra算法、Nordbeck提出的椭圆限制搜索区域改进算法[2]。随着计算数据的海量化以及摩尔定律的失效(晶体管电路已经接近了其物理改进的极限)，串行算法本身的改进和组合已不能适应需求。计算机科学领域出现了另一类并行最短路径分析算法设计，目前关于并行最短路径分析算法设计有基于MPI的主从Dijkstra并行算法[3]、MPI+open-MP混合算法[4]、社区分析的最短路径LC-2q并行算法[5]等。本文针对物流及时配送和成本控制需求，提出基于标色法的MapReduce广度优先算法并行化模型，并应用于配送线路优化问题。由于MapReduce本身封装了数据分割、负载均衡、容错处理等细节，用户只需要将实际应用问题分解成若干可并行操作的子问题，有效降低了求解难度，为解决物流配送运输路径优化问题提供了技术支持。1 MapReduce算法描述信息技术和网络技术的发展为云计算的产生提供了条件。MapReduce并行编程模型是云计算的核心技术之一。MapReduce是Google 实验室提出的一个分布式并行编程模型或框架, 主要用来处理和产生海量数据的并行编程模式，2004 年DEAN J和GHEMAWAT S第一次发表了这一新型分布式并行编程模型[6]。用户不必关注MapReduce 如何进行数据分割、负载均衡、容错处理等细节，只需要将实际应用问题分解成若干可并行操作的子问题，这种分解思路遵守主从架构模型。Mapreduce框架的主要程序分为Master、Map和Reduce。在Hadoop 中，MapReduce由一个主节点(Jobtracker,属于Master)和从节点(Tasktracker,属于Map和Reduce)组成[7]。1.1 基于标色法的MapReduce广度优先算法模型给定一个带权有向图,用G=(N，E，W)模型来表示，其中N={ni∣i=1,2，...，m}为完全图的点的集合；E={e(ni,nj)∣i≠j, ni,nj∈N}为弧段集；W={w(ni,nj)∣i≠j,ni,nj∈N}为权值集。一般向图的权值表示节点与节点之间的几何长度,记为w(ni,nj)=dij，dij表示节点ni到节点nj的距离。最短路径计算就是计算从起始点ni到终止点nj的最短几何长度之和为最小。在有向图起始点和终止点的最短路径计算中，MapReduce采用的是广度优先算法。MapReduce计算最短路径用邻接表来表示图，在邻接表中每一行数据构成Map和Reduce的一个数据内容。Map和Reduce的(key，value)中key为N，value值为与这个节点邻接的所有节点的 AdjacentList。在用标色法求解最短路径时，AdjacentList节点的信息包括源点到顶点的距离distance(除到本身的距离为0外，其余初始值皆为无穷大)；节点的颜色color(其值可分别取0、1、2，0表示未处理的顶点，1表示等待处理的顶点，2表示已处理的顶点，源点的初始值为1，其余顶点皆为0)；被访问顶点和边的权值记为N和W。顶点的数据结构如表1所示。
遗传算法基本原理111
第二章遗传算法的基本原理 2.1 遗传算法的基本描述 2.1.1 全局优化问题 全局优化问题的定义：给定非空集合S作为搜索空间，f：S—>R为目标函数，全局优化问题作为任务给出，即在搜索空间中找到至少一个使目标函数最大化的点。 全局最大值（点）的定义：函数值称为一个全局最大值，当且仅当成立时，被称为一个全局最大值点（全局最 大解）。 局部极大值与局部极大值点（解）的定义： 假设在S上给定了某个距离度量，如果对，，使得对， ，则称x’为一个局部极大值点，f(x’)为一个局部极大 值。当目标函数有多个局部极大点时，被称为多峰或多模态函数（multi-modality function）。 主要考虑两类搜索空间： 伪布尔优化问题：当S为离散空间B L={0,1}L,即所有长度为L且取值为0或1的二进制位串的集合时，相应的优化问题在进化计算领域称为伪布尔优化问题。 连续参数优化问题：当取S伪n维实数空间R n中的有界集合，其中，i = 1, 2, … , n时，相应的具有连续变量的优化问题称为连续参数优化问题。 对S为B L={0,1}L，常采用的度量时海明距离，当时，常采用的度量就是欧氏距离。 2.1.2 遗传算法的基本流程
遗传算法的基本步骤如下： 1）选择编码策略，把参数集合X和域转换为位串结构空间S； 2）定义适应度函数f(X)； 3）确定遗传策略，包括群体规模，选择、交叉、变异算子及其概率。 4）生成初始种群P； 5）计算群体中各个体的适应度值； 6）按照遗传策略，将遗传算子作用于种群，产生下一代种群； 7）迭代终止判定。 遗传算法涉及六大要素：参数编码，初始群体的设定，适应度函数的设计，遗传操作的设计，控制参数的设定，迭代终止条件。 2.1.3 遗传编码 由于GA计算过程的鲁棒性，它对编码的要求并不苛刻。原则上任何形式的编码都可以，只要存在合适的对其进行操作的遗传算子，使得它满足模式定理和积木块假设。 由于编码形式决定了交叉算子的操作方式，编码问题往往称作编码-交叉问题。 对于给定的优化问题，由GA个体的表现型集合做组成的空间称为问题（参数）空间，由GA基因型个体所组成的空间称为GA编码空间。遗传算子在GA
遗传算法的应用研究_赵夫群
2016年第17期 科技创新科技创新与应用 遗传算法的应用研究 赵夫群 （咸阳师范学院，陕西咸阳712000） 1概述 遗传算法（Genetic Algorithms，GA）一词源于人们对自然进化系统所进行的计算机仿生模拟研究，是以达尔文的“进化论”和孟德尔的“遗传学原理”为基础的，是最早开发出来的模拟遗传系统的算法模型。遗传算法最早是由Fraser提出来的，后来Holland对其进行了推广，故认为遗传算法的奠基人是Holland。 随着遗传算法的不断完善和成熟，其应用范围也在不断扩大，应用领域非常广泛，主要包括工业控制、网络通讯、故障诊断、路径规划、最优控制等。近几年，出现了很多改进的遗传算法，改进方法主要包括：应用不同的交叉和变异算子；引入特殊算子；改进选择和复制方法等。但是，万变不离其宗，都是基于自然界生物进化，提出的这些改进方法。 2遗传算法的原理 遗传算法是从某一个初始种群开始，首先计算个体的适应度，然后通过选择、交叉、变异等基本操作，产生新一代的种群，重复这个过程，直到得到满足条件的种群或达到迭代次数后终止。通过这个过程，后代种群会更加适应环境，而末代种群中的最优个体，在经过解码之后，就可以作为问题的近似最优解了。 2.1遗传算法的四个组成部分 遗传算法主要由四个部分组成[1]：参数编码和初始群体、适应度函数、遗传操作和控制参数。编码方法中，最常用的是二进制编码，该方法操作简单、便于用模式定理分析。适应度函数是由目标函数变换而成的，主要用于评价个体适应环境的能力，是选择操作的依据。遗传操作主要包括了选择、交叉、变异等三种基本操作。控制参数主要有：串长Z，群体大小size，交叉概率Pc，变异概率Pm等。目前对遗传算法的研究主要集中在参数的调整中，很多文献建议的参数取值范围一般是：size取20~200之间，Pc取0.5~1.0之间，Pm取0~0.05之间。 2.2遗传算法的基本操作步骤 遗传算法的基本操作步骤为： （1）首先，对种群进行初始化；（2）对种群里的每个个体计算其适应度值；（3）根据（2）计算的适应度，按照规则，选择进入下一代的个体；（4）根据交叉概率Pc，进行交叉操作；（5）以Pm为概率，进行变异操作；（6）判断是否满足停止条件，若没有，则转第（2）步，否则进入（7）；（7）得到适应度值最优的染色体，并将其作为问题的满意解或最优解输出。 3遗传算法的应用 遗传算法的应用领域非常广泛，下面主要就遗传算法在优化问题、生产调度、自动控制、机器学习、图像处理、人工生命和数据挖掘等方面的应用进行介绍。 3.1优化问题 优化问题包括函数优化和组合优化两种。很多情况下，组合优化的搜索空间受问题规模的制约，因此很难寻找满意解。但是，遗传算法对于组合优化中的NP完全问题非常有效。朱莹等[2]提出了一种结合启发式算法和遗传算法的混合遗传算法来解决杂货船装载的优化问题中。潘欣等[3]在化工多目标优化问题中应用了并行遗传算法，实验结果表明该方法效果良好。王大东等[4]将遗传算法应用到了清运车辆路径的优化问题求解中，而且仿真结果表明算法可行有效。 3.2生产调度 在复杂生产调度方面，遗传算法也发挥了很大的作用。韦勇福等[5]将遗传算法应用到了车间生产调度系统的开发中，并建立了最小化完工时间目标模型，成功开发了车间生产调度系统模块，并用实例和仿真验证了该方法的可行性。张美凤等[6]将遗传算法和模拟退火算法相结合，提出了解决车间调度问题的混合遗传算法，并给出了一种编码方法以及建立了相应的解码规则。 3.3自动控制 在自动控制领域中，遗传算法主要用于求解的大多也是与优化相关的问题。其应用主要分为为两类，即离线设计分析和在线自适应调节。GA可为传统的综合设计方法提供优化参数。 3.4机器学习 目前，遗传算法已经在机器学习领域得到了较为广泛的应用。邢晓敏等[7]提出了将遗传算子与Michigan方法和基于Pitt法的两个机器学习方法相结合的机器学习方法。蒋培等[8]提出了一种基于共同进化遗传算法的机器学习方法，该方法克服了学习系统过分依赖于问题的背景知识的缺陷，使得学习者逐步探索新的知识。 3.5图像处理 图像处理是一个重要的研究领域。在图像处理过程中产生的误差会影响图像的效果，因此我们要尽可能地减小误差。目前，遗传算法已经在图像增强、图像恢复、图像重建、图像分形压缩、图像分割、图像匹配等方面应用广泛，详见参考文献[9]。 4结束语 遗传算法作为一种模拟自然演化的学习过程，原理简单，应用广泛，已经在许多领域解决了很多问题。但是，它在数学基础方面相对不够完善，还有待进一步研究和探讨。目前，针对遗传算法的众多缺点，也相继出现了许多改进的算法，并取得了一定的成果。可以预期，未来伴随着生物技术和计算机技术的进一步发展，遗传算法会在操作技术等方面更加有效，其发展前景一片光明。 参考文献 [1]周明，孙树栋.遗传算法原理及应用[M].国防工业出版社，1999，6. [2]朱莹，向先波，杨运桃.基于混合遗传算法的杂货船装载优化问题[J].中国船舰研究，2015：10（6）：126-132. [3]潘欣，等.种群分布式并行遗传算法解化工多目标优化问题[J].化工进展，2015：34（5）：1236-1240. [4]王大东，刘竞遥，王洪军.遗传算法求解清运车辆路径优化问题[J].吉林师范大学学报（自然科学版），2015（3）：132-134. [5]韦勇福，曾盛绰.基于遗传算法的车间生产调度系统研究[J].装备制造技术，2014（11）：205-207. [6]黄巍，张美凤.基于混合遗传算法的车间生产调度问题研究[J].计算机仿真，2009，26（10）：307-310. [7]邢晓敏.基于遗传算法的机器学习方法赋值理论研究[J].软件导刊[J].2009，8（11）：80-81. [8]蒋培.基于共同进化遗传算法的机器学习[J].湖南师范大学自然科学学报，2004，27（3）：33-38. [9]田莹，苑玮琦.遗传算法在图像处理中的应用[J].中国图象图形学报，2007，12（3）：389-396. [10]周剑利，马壮，陈贵清.基于遗传算法的人工生命演示系统的研究与实现[J].制造业自动化，2009，31（9）：38-40. [11]刘晓莉，戎海武.基于遗传算法与神经网络混合算法的数据挖掘技术综述[J].软件导刊，2013，12（12）：129-130. 作者简介：赵夫群（1982，8-），女，汉族，籍贯：山东临沂，咸阳师范学院讲师，西北大学在读博士，工作单位：咸阳师范学院教育科学学院，研究方向：三维模型安全技术。 摘要：遗传算法是一种非常重要的搜索算法，特别是在解决优化问题上，效果非常好。文章首先介绍了遗传算法的四个组成部分，以及算法的基本操作步骤，接着探讨了遗传算法的几个主要应用领域，包括优化、生产调度、机器学习、图像处理、人工生命和数据挖掘等。目前遗传算法以及在很多方面的应用中取得了较大的成功，但是它在数学基础方面相对还不够完善，因而需要进一步研究和完善。 关键词：遗传算法；优化问题；数据挖掘 67 --