Chapter 2 遗传算法 TSP问题.pdf

背景 Holland的基本遗传算法 计算举例 GA的各种变形和改进 应用举例 1.遗传算法 (GA)的产生与发展  早在50年代，一些生物学家开始研究运用数字计算机模拟 生物的自然遗传与自然进化过程；  1963年，德国柏林技术大学的I. Rechenberg和H.P. Schwefel ， 做风洞实验时，产生了进化策略的初步思想；  60年代， L. J. Fogel在设计有限态自动机时提出进化规划的 思想。1966年Fogel等出版了 《基于模拟进化的人工智能》， 系统阐述了进化规划的思想。 1.遗传算法 (GA)的产生与发展  60年代中期，美国Michigan大学的J. H. Holland教授提出借 鉴生物自然遗传的基本原理用于自然和人工系统的自适应行 为研究和串编码技术；  196 年，他的学生J.D. Bagley在博士论文中首次提出 “遗传 算法(Genetic Algorithms)”一词；  1975年，Holland出版了著名的 “Adaptation in Natural and Artificial Systems” ，标志遗传算法的诞生。 1.遗传算法 (GA)的产生与发展  70年代初，Holland提出了 “模式定理” （Schema Theorem），一 般认为是 “遗传算法的基本定理”，从而奠定了遗传算法研究的理 论基础；  1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际 遗传算法学会( I S G A ，I n t e r n a t i o n a l S o c i e t y o f G e n e t i c Algorithms) ；  1989年，Holland的学生D. J. Goldherg出版了 “Genetic Algorithms in Search, Optimization, and Machine Learning” ，对遗传算法及其 应用作了全面而系统的论述；  1991年，L.Davis编辑出版了 《遗传算法手册》，其中包括了遗传算 法在工程技术和社会生活中大量的应用实例。 2.遗传算法 (GA)的来源： 生物的进化：自然选择、适者生存 达尔文的自然选择说) 生物的遗传和变异 生物遗传概念在遗传算法的对应关系 生物遗传概念 遗传算法中的作用 适者生存 在算法停止时，最优目标函数值的解有最大的可 能性被保留 个体 解 染色体 解的编码 字符串，向量等) 基因 解中每一个分量的特征 如各个分量的值) 适应性 适应函数值 群体 选定的一组解 其中解的个数为群体的规模) 种群 根据适应函数值选取的一组解 交配 通过交叉原则产生一组新解的过程 变异 编码的某一个分量发生变化的过程 3. 遗传算法的基本思想 根据问题的目标函数构造适值函 数 (Fitness Function)； 产生一个初始种群； 根据适值函数的好坏，不断选择 繁殖； 若干代后得到适值函数最好的个 体即最优解。 4.遗传算法的构成要素 ① 种群 (Population), 种群大小 (Pop-size) ② 基因表达法——编码方法 (Encoding Scheme; Gene Representation) ③ 遗传算子 (Genetic Operator)： 交叉(Crossover)，变异(Mutation) ④ 选择策略:一般为正比选择 ⑤ 停止准则 (Stopping Rule/Crite