资源描述：
《整数规划问题智能求解算法综述_杜祜康》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、第27卷第2期计算机应用研究Vol.27No.22010年2月ApplicationResearchofComputersFeb.2010＊整数规划问题智能求解算法综述杜祜康,赵英凯(南京工业大学自动化与电气工程学院,南京210009)摘要:为了对大规模整数规划问题的求解方法提供参考,对基于智能算法求解整数规划问题的研究进行了分析和评述。鉴于现有算法的缺陷与不足,讨论了应用智能算法求解整数规划问题未来可能的研究方向。关键词:整数规划;遗传算法;分布估计算法;粒子群算法;蚁群算法;DNA计算;问题求解中图分类号:TP301文献标志码:A
2、文章编号:1001-3695(2010)02-0408-05doi:10.3969/j.issn.1001-3695.2010.02.003SurveyonintelligentoptimizationalgorithmsforsolvingintegerprogrammingproblemsDUHu-kang,ZHAOYing-kai(SchoolofAutomation＆ElectricalEngineering,NanjingUniversityofTechnology,Nanjing210009,China)Abstract:
3、Inordertoprovidereferenceofwaysforsolvinglarge-scaleintegerprogrammingproblems,thepapermadeananaly-sisandcommentonresearchofsolvingintegerprogrammingproblemsbasedonintelligentalgorithms.Inviewoftheshortcom-ingsofcurrentalgorithms,discussedsomepossiblefutureresearchdirec
4、tionsaboutintelligentoptimizationalgorithmsforsol-vingintegerprogrammingproblem.Keywords:integerprogramming(IP);geneticalgorithms(GA);estimationofdistributionalgorithms;particleswarmopti-mization;antcolonyoptimization;DNAcomputing;problem-solving划解法的单点搜索效率低的问题,在实际优化问题应用
5、中具有引言较大的灵活性,对大规模的整数规划问题的求解较为有效。本整数规划(IP)和混合整数规划(mixedintegerprogramming,文主要对智能优化算法在求解整数规划问题中的应用进行分MIP)问题是运筹学领域里的一个重要分支,机械、化工、计算析总结,以期对大规模整数规划问题的求解提供方法参考,并机、经济、生物、军事、社会等各个学科领域里的许多优化问题在文章最后给出了关于整数规划问题求解的思考与展望。均可归结为IP或MIP问题,且大多数的组合优化问题都可以整数规划问题求解的群体智能优化算法写成一个IP或MIP问题,如背包、旅
6、行商、最短路、选址、分配和生产与存储计划问题等。因此如何求解IP或MIP问题是一群体智能优化算法是一类从生物群体的角度对智能进行个重要的研究领域。虽然整数规划问题的解空间在结构上比模拟的随机搜索算法,主要包括遗传、分布估计、粒子群和蚁群连续问题好确定,但其解的计算却十分困难。尽管持续不断的算法等。它不依赖于梯度信息的群体搜索策略及群体中个体理论研究已有几十年时间,加之计算机速度和功能的惊人增之间信息交换的特点,可以用来解决许多传统搜索方法解决不加,整数规划求解算法的研究还是没能达到令人十分满意的结了的复杂问题,对求解可行解区域为离散点
7、的大规模整数规划果。由于整数规划问题的可行解区域为离散点,故一般不能用问题十分有效。连续区域的求解算法,只能用特殊方法求解,应用较多的传统.基于遗传算法的整数规划问题求解[1][2]方法是分支定界法(branchandboundmethod)、割平面法[10,11][3～5]遗传算法(GA)是模拟生物在自然环境中的遗传和(cuttingplanealgorithm)和分解算法(decompositionalgo-rithm),其他常规方法有图论法[6]、交集及交集余集解法[7]、罚进化过程而形成的一种自适应全局优化的概率算法。在遗传函
8、数法[8]、群论法[9]等。算法中,用种群表示优化问题的一组候选解,种群中的每个个传统的整数规划问题的求解算法是一种确定性算法,即从体都有相应的适应值,然后反复进行选择、交叉和变异等模拟一个搜索点到另一个搜索点的转移有确
