遗传算法及其工程应用
史 斌
1
, 张 亮
1
, 郭芳健
1
, 丁 慧
1
(泰安市公安消防支队, 山东 泰安 271000)
摘要: GA 是基于自然选择和遗传机制, 在计算机上模拟生物进化机制的搜索寻优算法。论述了遗传算法 的遗
传编码、遗传算子和评价函数, 并采用遗 传算法实现商品调度。给出了算法步骤, 并与其它算法作了比较。
关键词: 遗传算子, 遗传编码, 商品调度
中图分类号: T P 301 文献标识码: A 文章编号: 1000- 2324 ( 2010) 03- 0443- 04
收稿日期: 2010- 01- 10
作者简介: 史 斌 ( 1976- ) 男 高级工程师 主要从事计算机应用研究 。
GENETIC ALGOR ITHM AND ITS ENG INEER ING APPLICATIONS
SH I B in, ZHANG L iang
1
, GUO Fang- jian
1
, D ING H ui
1
(T aia'n Fire D etachm en t , Shandong Taian 271000, Ch ina)
Abstract: Based on the natural selection and genetic m echan ism, Genetic a lgorithm simu late optim ization bio
log ica l evo lut ion m echan ism s on the com puter. ofD iscusses the genetic coding genetic a lgorithm, genetic oper
ators and evaluation functions, and product schedu ling by genetic algorithm. G iven algo rithm steps, and com
pared w ith other algorithm s.
K ey w ord s: G enetic operators; genetic cod ing; dispatch of goods
1 遗传算法的基本原理
遗传算法 ( Genetic A lgorithm, 简称 GA ) 是生命科学与工程科学相互交叉、相互渗透的结果。它启
迪于自然界生物从低级、简单, 到高级、复杂, 以及人类这样一个漫长而充满奥秘的进化过程, 同时借
鉴了达尔文的物竞天择、优胜劣汰、适者生存的自然选择和自然遗传机理, 并将其引入编码串结构, 在
串与串之间进行有组织的但又是随机的信息交换, 优良的品质被逐渐保留并加以组合, 从而不断产生出
更优的个体, 其本质是一种求解问题的高效并行全局的搜索方法。
自 20世纪 60年代中期美国 M ich igan大学 H o lland教授提出遗传算法 ( Genetic A lgorithm, 简称 GA )
以来, 其应用研究越来越深入, 应用领域也越来越广泛。遗传算法在智能控制系统设计、组合优化、模
式识别、机器学习、规划策略、信号处理和生命领域的应用中显示出其无以伦比的优越性和魅力。
GA 是基于自然选择和遗传机制, 在计算机上模拟生物进化机制的搜索寻优算法。在自然界的演化
过程中, 生物体通过遗传、变异来适应外界环境, 一代又一代地优胜劣汰、繁衍进化。GA 模拟了上述
进化现象, 它把搜索空间 ( 所求问题的解的隶属空间 ) 映射为遗传空间, 即把每一个可能的解编码为
一个向量, 称为一个染色体或个体, 向量的每个元素称为基因, 所有染色体组成群体或种群, 并按预定
的目标函数对每个染色体进行评价, 据其结果给出一个适应度的值。算法开始时先随机地产生一些染色
体 (所求问题的侯选解 ), 计算其适应度, 根据适应度大小对诸染色体进行选择、交叉、变异等遗传操
作, 剔除适应度低 (性能不佳 ) 的染色体, 留下适应度高 (性能优良 ) 的染色体, 从而得到新的群体。
由于新群体的成员是上一代群体的优秀者, 继承了上一代的优良性能, 因而明显优于上一代。 GA 就通
过这样的反复地操作, 向着更优解的方向进化, 知道满足某种预定的优化收敛指标。GA 是一个重复的
搜索过程, 但这一过程并不简单地重复搜索, 而是一个带着 记忆 的搜索, 算法本身使搜索不会向
山东农业大 学学报 (自然科学版 ), 2010, 41 ( 3): 443- 446
Journa l o f Shandong A g ricu ltura lU n iversity ( N atural Sc ience)
评论1