求解整数规划问题的混合遗传算法和收敛性.pdf

2009年 9月 高 等 学 校 计 算 数 学 学 报 第 3l卷第 3期 求解整数规划问题的混合遗传 算法及收敛性 郭仁拥 (内蒙古大学计算机学院，呼和浩特 010021) 金海和 (内蒙古大学公共管理学院，呼和浩特 010021) A HYBRID GENETIC ALGoRITHM FoR INTEGER PRoGRAM M ING AND ITS CoNVERGENCE GuoRenyong (CollegeofComputerScience，InnerMongoliaUniversity,Hohhot010021) JinHaihe (SchoolofPublicManagement，InnerMongoliaUniversity,Hohhot010021) Abstract In thispapera hybrid genetic algorithm forintegerprogramm ing， which integratesboth ageneticalgorithm and a simulated annealingalgorithm byanew method toavoidlargedropofthealgorithm ’Sefficiencyisproposed．A new “natureselect”ruleisaddedintothealgorithm toensurethatitconvergesto optimalsolutionwithprobability1．And alsoindividualsmorethanonearegen— eratedbyapairofparentstoimproveindividuals’diversityandalgorithm’Slocal searchability．Thealgorithm’SconvergenceisprovedusingthetheoryofMarkov chain，andeffectivenessisexaminedbyseveralnumericalexperiments． Key words hybridgeneticalgorithm ，integerprogramming，Markovchain AMS(2000)subjectclassifications 90C30 中图法分类号 O241．6 收稿 日期：2006-04-16 222 · 郭仁拥等：求解整数规划问题的混合遗传算法及收敛性 第 3期 1 引 言 科学和工程领域中的许多优化问题最终可以归结为求解一个带有约束条件的整数规 划问题．其形式为 ： max ，() 矧 S．t． gi(x)=0， i=1，·一，me； gi(x) 0， i：me+1，… ，m ∈IIAi． 式中 表示整数集，X=(Xl，… ， )TA(∈{1，… ，佗})为有限整数集． 遗传算法作为一种优化技术，是一种近似算法，一般不能保证一定能得到优化问题的 精确解．为了提高算法的精确度，人们提出许多改进算法，例如遗传模拟退火算法 【、“优 胜劣汰”遗传算法 [2】、基于最优保存和 自适应的遗传算法 [3】等． 遗传算法的局部有哪些信誉好的足球投注网站能力较差，但把握有哪些信誉好的足球投注网站过程总体的能力较强．模拟退火算法 [】 具有较强的局部有哪些信誉好的足球投注网站能力，并能使有哪些信誉好的足球投注网站过程避免陷入局部最优解．将遗传算法与模拟退火 算法相