Developments of High Performance Memetic Algorithms for Combinatorial Optimization Problems

组合优化问题的高性能模因算法的发展

• 批准号: 21500229
• 负责人: KATAYAMA Kengo
• 金额: $ 3万
• 依托单位: Okayama University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2009
• 资助国家: 日本
• 起止时间: 2009 至 2011
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21500229/
• 关键词: 組合せ最適化; メタ戦略; 進化計算; 局所探索; 最大クリーク問題; ノード配置問題; 2次割当問題

In our research, we developed high-performance metaheuristic algorithms called memetic algorithms for combinatorial optimization problems. As combinatorial optimization problems, we deal with the Maximum Clique Problem(MCP), Quadratic Assignment Problem(QAP), and Node Placement Problem(NPP), which are known to be NP-hard. Particularly, for the QAP, we show an effective metaheuristic algorithm called genetic iterated local search(GILS) incorporating k-opt local search based on the idea of variable depth search. Computational results showed that the GILS with KLS obtained good results on average in comparison to standard iterated local search metaheuristic algorithms for the QAP.

在我们的研究中，我们开发了高性能的元启发式算法称为模因算法的组合优化问题。作为组合优化问题，我们处理的最大团问题（MCP），二次分配问题（QAP），和节点放置问题（NPP），这是已知的NP-难。特别是，对于QAP，我们展示了一种有效的元启发式算法，称为遗传迭代局部搜索（GILS），将k-opt局部搜索的基础上，变深度搜索的想法。计算结果表明，与标准的迭代局部搜索元启发式算法的QAP相比，GILS与KLS平均取得了良好的效果。

项目成果

最大クリーク問題に対する反復k-opt局所探索法のKick法におけるタイブレーク時の頂点選択方式の検討

最大团问题迭代 k-opt 局部搜索方法 Kick 方法中抢七时顶点选择方法的检验

• 发表时间: 2010
• 期刊: 岡山理科大学紀要
• 作者: 幸村明典;片山謙吾;南原英生
• 通讯作者: 南原英生

2次割当問題に対する k-opt 局所探索法の有効性

k-opt 局部搜索方法对于二次分配问题的有效性

• 发表时间: 2009
• 作者: 三好亮介;前田裕;三好誠司;北田雅享
• 通讯作者: 北田雅享

最大クリーク問題に対する局所探索法の頂点選択方式に関する基礎検討

最大团问题局部搜索法顶点选择方法的基础研究

• 发表时间: 2011
• 作者: 渡邉好幸;片山謙吾;南原英生
• 通讯作者: 南原英生

最大クリーク問題に対する反復局所探索法の局所解脱出法の検討

最大团问题迭代局部搜索方法的局部解转义方法检验

• 发表时间: 2009
• 作者: 幸村明典;片山謙吾;南原英生;成久洋之
• 通讯作者: 成久洋之

ノード配置問題に対するアント最適化法

节点放置问题的蚂蚁优化方法

• 发表时间: 2010
• 期刊: 電子情報通信学会技術研究報告 NS2010-134
• 作者: 大倉慶一;片山謙吾;舩曵信生;南原英生;西原典孝
• 通讯作者: 西原典孝