《整体退火遗传算法及其收敛充要条件》由会员分享，可在线阅读，更多相关《整体退火遗传算法及其收敛充要条件（11页珍藏版）》请在金锄头文库上搜索。
1、第卷第期中旧种李辑年月整体退火遗传算法及其收敛充要条件张讲社徐宗本夕刃、协月又口西安交通大学理学院信息与系统科学研究所 西安香港中文大学环境研究中心摘要针对常用时齐比例选择 下遗传算法的强不收敛性和难以设置合理停机准则的弊端,提 出一类非时齐整体退火选择下、保证收敛且容易判断收敛 的新型遗传算法,证明允许父代参加竞争是这类新算法收敛 的充要条件数值实验表明这类新算法收敛速度快,有极强的避免过早收敛及避免局部极值 的全局优化能力关词遗传算法棋拟进化计算计算智能退火选择过程“物竟天择”的自然进 化过程在计算机 上的模拟 产生了一类 优化算法模拟进 化算法川遗传算法便是这类算法中最为重要的一类通常,
2、这一算法被描述作求解组合优化问题 鹭,一,“,其 中十为一实值映射这类算法已在人工智能、神经网络、知识库维护以及众多的工程应用领域显示了其解决复杂 问题的特别能力一,因此正引起 各学科对这类算法的普遍兴趣,作为一种优化算法及其机器学习算法,遗传算法具有深刻的生物背景和广泛的应用前景但相比之下,它的数学基础却相当薄弱以”这一状况特别表现 在算法的收 敛性分析上迄今为止,有关遗传算法的收敛性结果仅包括文献【 证 明了一类抽象遗传算法 的收敛性文献【在种群规模无穷的条件下分析了典型遗传算法 的收敛性文献【证明了原始遗传算法不收敛,而所有历代种群 中的最好个体适应值以概率为收敛到最优值我们注意到,种群
3、规模无穷的假设破坏了遗传算法的可实现性,而记录历代种群的最好个体仅 为一种独立于算法自身的外部记录,它对遗传算法本身无任何改进,故一般遗传算法的收敛性分析以及如何构造一个收敛的遗传算法仍是这一领域急需解决的重要理论 问题另外,作为一种普遍适用的、随机大范围搜索策略,现有遗传算法有收敛速度慢,不能绝对保证不陷于局部极值,常常出现过早收敛,没有判定 当前解是否达到最优解的合理准则 从而,没有合理 的停机准则等缺陷本文提出一个收敛的、在相当大程度上可克服以上缺陷的新型遗传算法通过发展一般遗传算法的一个清晰的链表示,首先简洁证明常用的标准遗 传算法无论是 否允许其父代参加竟争,均强不收敛然后,通过引入
4、一类时变选择策略一整体退火选择,证明对于采一一收稿,一收修改稿,国家自然科学荃金和“八六三”计划 资助项目第期张讲社等整体退火遗传算法及其收敛充要条件用这一选择下的遗传算法,允许其父代参加竟争是算法 收敛的充要条件由此我们获得一个整体收敛的新遗传算法整体退火遗传算法这类算法不仅保证收敛,而且比标准遗传算法有快得多的收敛速度,有更强的逃脱局部极值和避免过早收敛的全局优化能力另外,新算法所产生种群的每一个体都将以概率收敛到整体最优解,从而种群适 应值的集中程度可 自然作为判定当前解是否达到最优的合理标度遗传算法及其链表示遗传算法是一类群体搜索策略,所谓群体是指状态空间的有限点集依照生物学术语,将中
5、任一有限点集,。称为一个种群,称为该种群的规模中任一点“称为一个个体或染色体,而中每一二或称之为基因如果为一严格单增函数且使二,则称为问题的一个适应度函数设一,一久和一,一是中两个种群我们用表示种群,一久,一一般 的遗传算法如下遗传算法“随机地选取初始种群尸。从种群尸中按适应度大小,随机地选取父本种群 凡,由经杂交产生杂交种群。,变异得中间种群“,由父代种群和中间种群共同组成新的种群尸。、,凡、或以走作为新的种群尸,即尸,停机准则满足在上述算法的执行过程中,种群 凡 的规模。,和“的规模均为常数相应地,中种群尸,、的规模为。十、,中尸,的规模为步骤表示允许父代参加竟争繁殖,而步骤表示不允许父代
6、参加竞争繁殖上述遗传算法包含了标准遗传算法了和许多其他变形,遗传算法通常采用所谓的比例选择从种群尸中随机独立地选取。个个体作为新的父代种群若允许重复选取,则尸被选中的概率 为尸选取。卜,。习,瓦气气若不允许重复选取,则当“,气任已被选取后,按下述概率从集合玲一尸。“,气中选取下一个个体,尸选取。、一,。习,。,气心变异是按一确 定概率尸。随机独立地改变,中每个个体的每一基因若两个个体中国科学辑第卷,和之 间的距离为,则由变异到的概率为占一占尸龙“一走一杂交是作用在父代个不同的个体上,以概率的方式 产 生个或个新个体杂交有许多方式,但杂交的方式不影响下面的收敛性分析,故在此不再赘述,其具体细节可
7、参见文献【由于种群 凡中包 含。个中元素,故我 们可认 为凡 为、中一点类 似地,我们将。,“看作”中的点,尸为”或”中的点按照这 一看法,这些空间的任一点表示 一个种群,其坐标分量即为一个 个体 特别”。中任一元素均可作为父本若任,。是一从尸以任卜”或刀,中选出的种群,我 们记仁尸住若乞是中的一个个体,则记乞任遗传算法是一类随机方法,凡是一随机变量因此,算法的状态可 由 凡 在。上的概率分布来描述,而凡、的分布又由凡 的分布确定故遗传算法可由一链表示令”。,”“,一刀尸,尸,尸,尸“”,其中刀”。,分别表示空间。和刀”中的元素个数记,凡 。为父代种群空间、中的元素,二,为杂交种群 空间中的元
8、素,”,为中间种群空间”中的元素,。表示算法在第步 由“ 经杂交变 为,的概率,从,表示算法在第步由,经变异变为的概率,而盆才表示算法在第步,当父代为时,由中间种群尸耐变为新的父代种群“的转移概率则 由一卜公式知,算法在第步,由父代种群到新一代种群“的一步转移概率为若用走表示”。链表示。卜分蓉。、优公,“,。阶矩阵。,则遗传算法中凡 的分布变化可 由下述二,其 中,旧”。为一概率向量,表示 凡在。上的分布,左表示凡取状态,的概率根据杂交、变异和选择的定义,。,叽。和留具有以下性质二 艺。”。,掩,从,尸、九一尸一人,”,走,丧一。了,乃气,乙了,“,二尸二,其他,第期张讲社等整体退火遗传算法及
9、其收敛充要条件其中,。为,和”的对应个体之间的距离尸一或“,因为至少有一个司包含“,故由知篇,。了。,由遗传算法的链表示式知,在一个确定的遗传算法中,当适应度函数,变异概率氏以及杂交方式均不随变化时,城。和讼均与无关相应的为常数阵,故此时遗传算法所对应链为一时齐链下面,我们称这类遗传算法为时齐遗传算法迄今为止所使用的众多遗传算法均为时齐遗传算法文献【证明了父代不参加竞争时时齐遗传算法的强不收敛性下节我们简洁证明无论是否允许父代参加竞争,时齐遗传算法均是强不收敛的时齐遗传算法的强不收敛性先引入一些记号和定 义令一任,一整奢、,假设在空 间上 不 恒为常数,从而存在 一个任使得。错奢,故存在,一。
10、,。,。”。使得,自公定义设遗传算法 由式表示如果对任一初始分布,我们有又乏、门并口 则称遗传算法收敛,否则称其不收敛若存在使得二,我们称遗 乏一。 传算法强不收敛式意指以渐近概率包含中的点,而当时,相应的链遍历,从而式推出式恒不成立,故当充分大时,凡的取值相当于以分布随机抽样因此,当前种群凡 不提供任何收 敛信息以下,我们将证明时齐遗传算法均 强 不收敛设为一矩阵,若的所有元素均大于零,则称为一正矩阵转移概率阵为正矩阵的链具有下述性质 引理如果转移概率阵尸是一正矩阵,则链对任意的初始分布,均有,盛叨 且与初始分布无关利用引理,我们证明定理 无论是否允许父代参加竞争,时齐遗传算法总是强不收敛的
11、证设式为时齐遗传算法 的链表示,其中氏氏和貂貂中国科学辑第卷为一族与无关的常数根据引理和定义,我们仅需证明时齐链的转移概率 阵为一正矩阵令尸一一尸,尸叽阴故 由、和式得由式知一尸八,一日,一月,旧刀一月一日”一。一习 艺。城,瑞乙名胃一。乙瑞,少阴二少二明这样式 中的转移概率阵为一正矩阵注意到,这一证明过程仅用到性质一式,而与是否允许父代参加竟争无关,这即说明时齐遗传算法总不强收敛证毕定理一方面说明了自然进化过程中多状态存在的可能性,另一方面亦说明在遗传算法中引入非时齐选择的必要性遗传算法的一类非时齐选择退火选择改进遗传算法收敛性的方 法 之 一是将模拟退火思想溶于遗传算法这方面已有许 多尝试
12、,但已有工作均是将传统模拟 退 火过 程嵌入遗传算法,“,其形式更接近并行的模拟退火技术本文给出遗传算法和模拟退 火思想的另一种结合方式,这一方式仅在遗传算法的步骤中引入 一时变选择整体退 火选择我们将证明,就 采用这一选择 的遗传算法而言,允许其父代参加竟争是其收敛的充要条件退火选择与传统模拟退火算法中二者择一接受准则的不 同之处在于 它以概率 的方式从一个多点集凡中选取 一多点集凡,任凡被选入凡 的概率为选取,卜沙一几艺。少丁。气气其中 爪为渐趋干。的退 火温度相应地,遗传算法步骤中适应度函数变化为几,于是式变 为“一“,“、气,名了气”“,、,二尸阴,为简化讨论,假定变异概率尸和杂交方式
13、不随其它变化,并记,。,其旧月一旧一 、一习 习。城。公才走这样采用退火选择式 下的遗传算法可表示为如下链几为了分析退火选择下遗传算法 的收敛性先 引入一些记号和定义设一,一久。九。,记二,。第期张讲社等整体退火遗传算法及其收敛充要条件定义设,维向量,几满足或几,或,一几的第一个非零分量为正,则称不劣于,并记若,。满足,则称不劣于并记记一“”竺”,”,、一氏几且仔在”“更得、“、”,”“、”仁”,“这里,当允许父代参加竞争时,。十。,而不允许父代参加竟争时,二。由“”的定义知,若,则一,。 。满足,一”一。一黔,因此 有同样,若任,则存在尸,任”门半事实上仁使得一,久。任尸满足。,才爪从而有门
14、“必,任类似于式的讨论也可知,均非空定理退火选择准则式下遗传算法收敛的充要条件是允许其父代参加竞争证为简化讨论,下设单调减趋于零一般情形可类似证明充分性 设退火选择遗 传算法中允许父代参加 竟争,从而按照式 中的定 义,此 时式中的满足尸一“。阴记黔,一,乞且占共若任,、告,则由式知二而无论任或任,中均有,阴一个体。使得。因此,由式和尸一君二知认一且 ,“、几艺“,几、“。几艺气几占加,几。艺占尸了气一了一几镇一户几,于是。内曰月门一、一名 名岭二盆才镇艺盆子簇一。一户几少 二若去,。任,则 当仁尸,时,由式得沼、一且 占“几,气几一【“艺“气几”。、几。十,勺”。二。”。中国科学辑第卷由于至
15、少有一个尸使得“仁尸功,故有。记一, 名习,、,、答,、,、。,爪乙拼左多自户乙甭”笋户瓦丁百不艺走,则由链的性质知 十一名艺。钱艺艺。 乙艺。,“夕任一盛一任由于习名。“,艺 艺。 一艺己,一尸,盛少盛去一少钱因此艺 艺。、一尸一艺艺。 ,“夕一口一将式代入式,再由和式得尸一一尸一艺乙。 、习 艺。 ,毛去“在一。”,一“几现在我们证明,对于任一。,存在着。,使得当李时恒有一,、,。厂左乏尧一廿,一尸,介。下面分步证明式步我们首先 用反证法证明存在。使得式成 立若其不然,对任意的。均有“,最,一,一几。,则由 爪 的单调下降性和式得一一尸几簇一一几。、警“,将式代入式,我 们得由于。,由式知。“,警“,一卜警,簇一警尸。,一,此与假设式矛盾这样,存在一“。使得式成立卜山 一,、,才口 乙田厂左一廿乞。一。,故由式有尸刀十镇 鱼,一,爪,一,一“。最,一,一几。,第期张讲社等整体退火遗传算法及其收敛充要条件这说明,式当二时亦成立依此类推,我们可断言式对于所有 的均成立故存在着二。,使当时,式成立
