Improved Pareto Fitness Genetic Algorithm for multi-objective combinatorial optimization

doi:10.3778/j.issn.1002-8331.2009.08.014

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (8): 44-46.DOI: 10.3778/j.issn.1002-8331.2009.08.014

• 研究、探讨 • Previous Articles Next Articles

Improved Pareto Fitness Genetic Algorithm for multi-objective combinatorial optimization

YANG Kai-bing^1,2,LIU Xiao-bing²

1.College of Information Science and Engineering，Dalian Polytechnic University，Dalian，Liaoning 116034，China
2.CIMS Center，Dalian University of Technology，Dalian，Liaoning 116024，China

Received:2008-01-21 Revised:2008-04-16 Online:2009-03-11 Published:2009-03-11
Contact: YANG Kai-bing

求解多目标组合优化的改进Pareto适应度遗传算法

杨开兵^1,2,刘晓冰²

1.大连工业大学信息科学与工程学院，辽宁大连 116034
2.大连理工大学 CIMS中心，辽宁大连 116024

通讯作者: 杨开兵

Abstract

Abstract: Combining Pareto Fitness Genetic Algorithm（PFGA） with local search，an Improved Pareto Fitness Genetic Algorithm（IPFGA） for multi-objective combinatorial optimization is proposed.In the proposed algorithm，a local search procedure is applied to each solution generated by genetic operations.The concept of Pareto dominance is used in the local search procedure，and the idea of crowding distance in the external population is used to perform elitism.The experimental results show that the IPFGA，compared with the known PFGA，has faster convergent speed.

Key words: multi-objective combinatorial optimization, Pareto Fitness Genetic Algorithm（PFGA）, local search

摘要： 将Pareto适应度遗传算法（PFGA）与局部搜索相结合，提出了一种用于求解多目标组合优化问题的改进算法IPFGA，该算法基于Pareto支配关系对遗传操作产生的每一个个体进行局部搜索，并采取在外部群体中引入拥挤距离的精英选择策略。实验结果表明，与PFGA相比，IPFGA有更快的收敛速度。

关键词: 多目标组合优化, Pareto适应度遗传算法, 局部搜索

YANG Kai-bing^1,2,LIU Xiao-bing². Improved Pareto Fitness Genetic Algorithm for multi-objective combinatorial optimization[J]. Computer Engineering and Applications, 2009, 45(8): 44-46.

杨开兵^1,2,刘晓冰². 求解多目标组合优化的改进Pareto适应度遗传算法[J]. 计算机工程与应用, 2009, 45(8): 44-46.

[1]	XU Chenhua, LUO Zhuguang, WU Guanhong, LIU Bin. Grey Wolf Optimization Algorithm Based on Sine Factor and Quantum Local Search [J]. Computer Engineering and Applications, 2021, 57(24): 83-89.
[2]	HAO Xiang, HE Yichao, ZHU Xiaobin, ZHAI Qinglei. Discrete Hybrid Multi-verse Optimization Algorithm for Solving Discounted {0-1} Knapsack Problem [J]. Computer Engineering and Applications, 2021, 57(18): 103-113.
[3]	YAN Miaomiao, LIU Sanyang. Multi-Classes Interaction Teaching-Learning-Based Optimization Algorithm [J]. Computer Engineering and Applications, 2019, 55(9): 10-16.
[4]	LIU Chunmiao, ZHANG Huizhen. Hybrid bat algorithm for un-capacitated facility location problem [J]. Computer Engineering and Applications, 2018, 54(22): 28-34.
[5]	DONG Xiaoshuai1，2，3, MAO Zhengyuan1，2，3. Research on solution of dynamic Vehicle Routing Problem based on improved genetic algorithm [J]. Computer Engineering and Applications, 2018, 54(19): 49-55.
[6]	WU Congcong1, ZHAO Jianli1，2, LIU Xuejing1, CHEN Yiying1. Modified differential evolution algorithm for solving multidimensional knapsack problem [J]. Computer Engineering and Applications, 2018, 54(11): 153-160.
[7]	HU Wei1,2, ZENG Bin1, YAO Lu1. Algorithm on deployment of monitoring station focused on key sea area driven by events [J]. Computer Engineering and Applications, 2017, 53(7): 136-140.
[8]	SONG Qiang. Application of improved iterated local search algorithm in MMTVRP [J]. Computer Engineering and Applications, 2017, 53(7): 248-255.
[9]	HONG Jianke1, ZHANG Zhenghua2, XU Guiping2. SAT local search algorithm based on enhanced probability controlling strategies [J]. Computer Engineering and Applications, 2017, 53(14): 56-60.
[10]	WANG Meng, FAN Kun, ZHAI Yafei, LI Xinning. Study of multiprocessor task scheduling problem in network parallel computing system [J]. Computer Engineering and Applications, 2017, 53(10): 264-270.
[11]	WU Yanlian1，2, JIANG Haiyan1，2, ZHUANG Jiaxiang1, GUO Xiaoqing1, XU Yihua1. Research of individual advantages genetic algorithm based on elitist strategy [J]. Computer Engineering and Applications, 2016, 52(7): 143-149.
[12]	LIN Geng1, XU Meiqin2. Discrete filled function method for max-bisection problem [J]. Computer Engineering and Applications, 2016, 52(5): 27-32.
[13]	LU Yuming1，4, WANG Yanchao2, LIU Jiarui3, Wu Liu4. Improved biogeography-based optimization algorithm [J]. Computer Engineering and Applications, 2016, 52(17): 146-151.
[14]	HU Bo. Multi-model function optimization based on immune clonal optimization with uniform design [J]. Computer Engineering and Applications, 2015, 51(2): 57-59.
[15]	HU Min1, HU Bo1, HUANG Hongmei2. Multicast routing optimization based on immune Memetic algorithm [J]. Computer Engineering and Applications, 2013, 49(2): 105-108.

Improved Pareto Fitness Genetic Algorithm for multi-objective combinatorial optimization

求解多目标组合优化的改进Pareto适应度遗传算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics