一种用于进化算法历史计算数据的高效利用方法

J4 ›› 2016, Vol. 38 ›› Issue (01): 62-66.

一种用于进化算法历史计算数据的高效利用方法

闫盼，谭瑛，张建华

（太原科技大学工业与系统工程研究所,山西太原 030024）

收稿日期:2014-11-12 修回日期:2015-04-24 出版日期:2016-01-25 发布日期:2016-01-25
基金资助:
国家自然科学基金(61472269,61403272)

A method of using historical calculation data
efficiently in evolutionary algorithms

YAN Pan,TAN Ying,ZHANG Jianhua

(Institute of Industrial and System Engineering,Taiyuan University of Science and Technology,Taiyuan 030024,China)

Received:2014-11-12 Revised:2015-04-24 Online:2016-01-25 Published:2016-01-25

摘要/Abstract

摘要：

进化算法由于其强大的系统建模能力和空间搜索能力已被广泛应用于许多实际问题的求解中。然而，在算法进化的过程中存在个体适应值重复计算的问题，尤其在解决实际工程中的复杂问题时，适应值的计算会消耗大量时间。为此，利用哈希表的高速存取能力，将哈希表用于存取适应值的历史计算数据，从而避免优化过程中适应值的重复计算，并且对优化结果没有任何影响。仿真实验结果验证了此方法的有效性。

关键词: 哈希表, 历史计算数据, 进化算法

Abstract:

Evolutionary algorithms have been widely used in practical problems for their remarkable system modeling capability and spatial searching capability. However, there is a problem of repetitive computation for individual fitness in the process of evolutionary algorithms. Especially when solving complex engineering problems, fitness calculations can expend a large amount of time. The hash table features highspeed access capability, which can be used to access historical data of fitness and solve repetitive computation problem of individual fitness during the optimization process without affecting the results. Simulation results prove the efficiency of the proposal.

Key words: hash table;historical calculation data;evolutionary algorithms

闫盼，谭瑛，张建华. 一种用于进化算法历史计算数据的高效利用方法[J]. J4, 2016, 38(01): 62-66.

YAN Pan,TAN Ying,ZHANG Jianhua. A method of using historical calculation data
efficiently in evolutionary algorithms [J]. J4, 2016, 38(01): 62-66.

参考文献［11］

［1］	Yao Xin,Chen Guoliang,Xu Huimin,et al.A survey of evolutionary algorithms［J］.Chinese Journal of Computers,1995,18(9):694706.(in Chinese)
［2］	Gong Maoguo, Jiao Licheng, Yang Dongdong,et al.Research on evolutionary multiobjective optimization algorithms［J］.Journal of Software,2009,20(2):271289.(in Chinese)
［3］	Xi Yugeng,Chai Tianyou,Yun Weimin.Survey on genetic algorithm［J］.Control Theory and Applications,1996,13(6):697708.(in Chinese)
［4］	Zeng Jianchao,Cui Zhihua.Natural computing ［M］.Beijing:National Defense Industry Press,2012.(in Chinese)
［5］	Shi Lijuan.Memory genetic algorithms in the application of function optimization ［D］.Suzhou:Soochow University,2010.(in Chinese)
［6］	Yan Weimin,Wu Weimin.Data structure (C language version) ［M］.Beijing:Tsinghua University Press,2009.(in Chinese)
［7］	Zhang Zhaoxia,Liu Yaojun.Effective solution to Hash collision［J］.Journal of Computer Application,2010,30(11):29652967.(in Chinese)
［8］	Ma Rulin,Jiang Hua,Zhang Qingxia.An improved fast searching method of Hash table［J］.Computer Engineering & Science,2008,30(9):6668.(in Chinese).
［9］	Yuan Liwei,Liu Fuxian,Zhao Baojun.Improved GA and its application to knapsack problem ［J］.Systems Engineering and Electronics,2005,27(4):718719.(in Chinese)
［10］	Gavish B,Graves S C.The travelling salesman problem and related problems［Z］.Rochester:University of Rochester,1979.
［11］	Zhou Huiren,Tang Wansheng,Wang Hailong.Optimization of multiplc traveling salesman problem based on differential cvolution algorithm［J］.Systems EngineeringTheory & Practice,2010,30(8):14711476.(in Chinese)
	附中文参考文献:
［1］	姚新,陈国良，徐惠敏.进化算法研究进展［J］.计算机学报,1995,18(9):694706.
［2］	公茂果,焦李成,杨咚咚,等.进化多目标优化算法研究［J］.软件学报,2009,20(2):271289.
［3］	席裕庚,柴天佑,恽为民.遗传算法综述［J］.控制理论与应用,1996,13(6):697708.
［4］	曾建潮,崔志华.自然计算［M］.北京:国防工业出版社,2012.
［5］	石丽娟.记忆遗传算法在函数优化中的应用［D］.苏州：苏州大学，2010.
［6］	严蔚敏,吴伟民.数据结构(C语言版)［M］.北京:清华大学出版社,2009.
［7］	张朝霞,刘耀军.有效的哈希冲突解决办法［J］.计算机应用,2010,30(11):29652967.
［8］	马如林,蒋华,张庆霞.一种哈希表快速查找的改进方法［J］.计算机工程与科学,2008,30(9):6668.
［9］	苑立伟,刘付显,赵保军.改进遗传算法及其在背包问题中的应用［J］.系统工程与电子技术,2005,27(4):718719.
［11］	周辉仁,唐万生,王海龙.基于差分进化算法的多旅行商问题优化［J］.系统工程理论与实践,2010,30(8):14711476.

[1]	闫盼，谭瑛，张建华. 一种用于进化算法历史计算数据的高效利用方法[J]. J4, 20160101, 38(01): 62-66.
[2]	张明珠, 曹杰, 王斌. 基于精英集的多目标差分进化聚类算法[J]. 计算机工程与科学, 2021, 43(01): 170-179.
[3]	胡福年，董倩男. 多策略自适应变异的差分进化算法及其应用[J]. 计算机工程与科学, 2020, 42(06): 1076-1088.
[4]	宋强1,刘亚萍2,刘珍兰1. 基于多代种群进化信息改进的差分进化算法研究[J]. 计算机工程与科学, 2018, 40(11): 2054-2059.
[5]	黄辉先，胡鹏飞. 基于共轭梯度法的反馈差分进化混合算法及其在弹簧设计中的应用[J]. 计算机工程与科学, 2018, 40(07): 1316-1322.
[6]	朱林波，汪继文，邱剑锋，方柳平. 基于简化群优化算法和协方差矩阵学习的差分进化算法[J]. 计算机工程与科学, 2017, 39(11): 2122-2130.
[7]	卢鹏飞1，王兴伟2，李福亮1，马连博2. 一种基于种族分类进化的QoS异构组播路由机制[J]. 计算机工程与科学, 2016, 38(08): 1633-1639.
[8]	徐曼舒，汪继文，邱剑锋，王心灵. 基于改进人工蜂群的模糊C-均值聚类算法[J]. J4, 2016, 38(06): 1238-1243.
[9]	王林1，彭璐1，夏德2，曾奕1. 自适应差分进化算法优化BP神经网络的时间序列预测[J]. J4, 2015, 37(12): 2270-2275.
[10]	张弛1，乐晓波1，周恺卿2，莫礼平3. 采用差分进化算法优化模糊Petri网参数[J]. J4, 2014, 36(06): 1095-1100.
[11]	朱高峰1，伍铁斌2,3，张艳蕾1，成运2，刘云连2. 一种求解约束优化问题的进化算法及其工程应用[J]. J4, 2013, 35(7): 95-101.
[12]	王林，冯云涛，富庆亮. 差分进化算法在模糊多资源约束联合补货模型中的应用[J]. J4, 2012, 34(1): 148-153.
[13]	敖友云1，迟洪钦2. 多目标优化差分进化算法[J]. J4, 2011, 33(9): 88-94.
[14]	曹炬,江兴稳. 基于近似梯度的宇宙大爆炸搜索算法[J]. J4, 2011, 33(2): 86-91.
[15]	许智宏,张竹楼,郭浩,李雪原. 双向主从式Chord资源搜索算法的研究[J]. J4, 2011, 33(11): 80-83.