一种求解冰壶比赛对阵多约束问题的逐层优化算法

doi:10.3969/j.issn.0372-2112.2017.03.019

电子学报 ›› 2017, Vol. 45 ›› Issue (3): 632-637.DOI: 10.3969/j.issn.0372-2112.2017.03.019

一种求解冰壶比赛对阵多约束问题的逐层优化算法

丁蕊^1,2, 董红斌¹, 邢薇¹, 刘文杰¹, 孔飞¹

1. 哈尔滨工程大学计算机科学与技术学院, 黑龙江哈尔滨 150001;
2. 牡丹江师范学院计算机与信息技术学院, 黑龙江牡丹江 157012

收稿日期:2015-08-03 修回日期:2016-02-23 出版日期:2017-03-25
- 作者简介:
- 丁蕊女,1977年8月出生于黑龙江鸡东.现为牡丹江师范学院讲师、博士研究生.CCF会员,主要研究方向为软件测试、演化算法、基于搜索的软件工程.E-mail:mdjdingrui@163.com;董红斌 男,1963年5月出生于河北唐山,现为哈尔滨工程大学教授,博士生导师.主要研究方向为自然计算、机器学习、多Agent系统、数据挖掘.E-mail:donghongbin@hrbeu.edu.cn
- 基金资助:
- 国家自然科学基金资助项目 (No.61472095，No.61272186）; 黑龙江省教育厅智能教育与信息工程重点实验室开放基金支持; 牡丹江师范学院青年项目 (No.QY2014003，No.QN201603）

An Hierarchic Optimization Algorithm for Curling-Match Multi-constrained Problem

DING Rui^1,2, DONG Hong-bin¹, XING Wei¹, LIU Wen-jie¹, KONG Fei¹

1. College of Computer Science and Technology, Harbin Engineering University, Harbin, Heilongjiang 150001, China;
2. School of Computer and Information Technology, Mudanjiang Normal University, Mudanjiang, Heilongjiang 157000, China

Received:2015-08-03 Revised:2016-02-23 Online:2017-03-25 Published:2017-03-25
- Supported by:
- National Natural Science Foundation of China (No.61472095, No.61272186); Open Fund of Key Laboratory of Intelligent Education and Information Engineering, Education Department of Heilongjiang Province; Youth Program of Mudanjiang Normal University (No.QY2014003, No.QN201603)

摘要/Abstract

摘要：

冰壶比赛对阵编排问题是一个难于收敛的多约束优化问题.为此提出一种求解此类问题的逐层优化的单亲遗传算法.首先将待求解问题的多个约束进行分层；其次设计了靶向自交叉算子进行第一层优化以提高搜索效率，设计了定点-随机自交叉算子进行第二层优化以保持种群的多样性；最后，将改进的算法用于解决冰壶比赛对阵编排的多约束优化问题，构建了该问题的适应度函数.仿真实验表明，与粒子群算法和经典遗传算法相比，所提算法能够有效求解冰壶比赛对阵编排的多约束优化问题.

关键词: 冰壶对阵多约束优化, 单亲遗传算法, 逐层优化, 靶向自交叉, 定点-随机自交叉

Abstract:

Curling-match design is a multi-constraint optimization problem which is hard to be converged.Therefore,a hierarchic optimization partheno-genetic algorithm is proposed.First,multiple constraint of the problem is layered;then,the targeted self-crossover operator is designed in the first layer optimization to ensure the convergence of the algorithm,while the fixed-random self-crossover operator is designed in the second layer optimization to maintain diversity of the population appropriately;finally,the proposed algorithm is used to solve the problem of curling-match design after building its fitness functions.Compared with the particle swarm algorithm and genetic algorithm,the simulation results demonstrate that the designed algorithm can solve the problem more efficiently.

Key words: curling-match multi-constrained optimization, partheno-genetic algorithm, hierarchic optimization, targeted self-crossover, fixed-random self-crossover

中图分类号:

TP18

丁蕊, 董红斌, 邢薇, 等. 一种求解冰壶比赛对阵多约束问题的逐层优化算法[J]. 电子学报, 2017, 45(3): 632-637.

DING Rui, DONG Hong-bin, XING Wei, et al. An Hierarchic Optimization Algorithm for Curling-Match Multi-constrained Problem[J]. Acta Electronica Sinica, 2017, 45(3): 632-637.

参考文献

[1] 玄光男,程润伟.遗传算法与工程优化[M].北京:清华大学出版社,2004.48-69.
[2] 王晟,李乐民.一种改进的多约束最佳路径算法研究[J].电子学报,2004,32(4):529-535. WANG Sheng,LI Le-min.An enhanced algorithm for multiple constraints optimal path calculation[J].Acta Electronica Sinica,2004,32(4):529-535.(in Chinese)
[3] 李茂军.单亲遗传算法理论及应用[D].长沙:湖南大学,2002.15-26.
[4] D E Goldberg.Genetic Algorithms in Search Optimization and Machine Learning[D].New Jersey:Addison Wesley,1989.
[5] R J Kuo,Y H Lee,F E Zulvia,et al.Solving bi-level linear programming problem through hybrid of immune genetic algorithm and particle swarm optimization algorithm[J].Applied Mathematics & Computation,2015,26(6):1013-1026.
[6] 王勇,蔡自兴,周育人,肖赤心.约束优化进化算法[J].软件学报,2009,20(1):11-29. WANG Yong,CAI Zi-xin,ZHOU Yu-ren,XIAO Chi-xin.Constrained optimization evolutionary algorithms[J].Journal of Software,2009,20(1):11-29.(in Chinese)
[7] LI Hongchen,XU Shuisheng,QS Chen.Investigation on the preparation for the curling match in 2009 winter universiade[J].China Winter Sports,2008,2008:4-16.
[8] Li M,Fan S,Luo A.A Partheno-genetic Algorithm for Combinatorial Optimization[M].Berlin Heidelberg:Springer Berlin Heidelberg,2004.224-229.
[9] Friedrich T,Wagner M.Seeding the initial population of multi-objective evolutionary algorithms:A computational study[J].Applied Soft Computing,2015,3(3):223-230.
[10] Q Long,C Wu,T Huang,X Wang.A genetic algorithm for unconstrained multi-objective optimization[J].Swarm & Evolutionary Computation,2015,2(2):1-14.
[11] Gang J,Tu Y,Lev B,et al.A Multi-objective bi-level location planning problem for stone industrial parks[J].Computers & Operations Research,2014,5(6):8-21.
[12] Miqing Li,Shengxiang Yang,Xiaohui Liu.Bi-goal evolution for many-objective optimization problems[J].Artificial Intelligence,2015,228(11):45-65.
[13] Gao L,Zhou Y,Li X,et al.Multi-objective optimization based reverse strategy with differential evolution algorithm for constrained optimization problems[J].Expert Systems with Applications,2015,42(14):5976-5987.
[14] Wei W,Wang J,Tao M.Constrained differential evolution with multi-objective sorting mutation operators for constrained optimization[J].Applied Soft Computing,2015,3(3):207-222.
[15] 孟庆春.带有对称编码的基因算法的研究[J].电子学报,1996,24(10):27-31. MENG Qin-chun.An approach on genetic algorithm with symmetric codes[J].Acta Electronica Sinica,1996,24(10):27-31.(in Chinese)

一种求解冰壶比赛对阵多约束问题的逐层优化算法

An Hierarchic Optimization Algorithm for Curling-Match Multi-constrained Problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	曹付元, 杨淑晶, 王雲霞, 俞奎. 基于约束的局部-全局LWF链图结构学习算法[J]. 电子学报, 2023, (): 1-11.
[2]	裴洪, 司小胜, 胡昌华, 郑建飞, 张建勋, 董青. 零寿命标签下退化设备剩余寿命预测方法[J]. 电子学报, 2023, (): 1-10.
[3]	吴翼腾, 刘伟, 于溆乔. 基于参数差异假设的图卷积网络对抗性攻击[J]. 电子学报, 2023, 51(2): 330-341.
[4]	许新征, 李杉. 基于特征膨胀卷积模块的轻量化技术研究[J]. 电子学报, 2023, 51(2): 355-364.
[5]	陈阳, 皮德常, 代成龙, 李本田, 王碧, 薛乔. 多无人机协同陆地设施辅助移动边缘计算的系统能耗最小化方法[J]. 电子学报, 2023, (): 1-9.
[6]	张重生, 王斌. 基于序列相似性计算的甲骨残片缀合算法[J]. 电子学报, 2023, (): 1-10.
[7]	郭晓轩, 冯其波, 冀振燕, 郑发家, 杨燕燕. 多线激光光条图像缺陷分割模型研究[J]. 电子学报, 2023, 51(1): 172-179.
[8]	闫梦宇, 李金海, 刘文奇, 张文修. 带对象结构信息形式背景的概念知识发现与演化[J]. 电子学报, 2023, 51(1): 11-17.
[9]	徐佳伟, 罗倩. 基于遗传非参数MDL-BW方法的HMM结构优化[J]. 电子学报, 2022, 50(11): 2765-2772.
[10]	智慧来, 张丽, 李金海. 旁观者视角下粒的多层次描述[J]. 电子学报, 2022, 50(11): 2568-2574.
[11]	赵嘉, 王刚, 吕莉, 樊棠怀. 面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法[J]. 电子学报, 2022, 50(11): 2730-2737.
[12]	刘浩阳, 林耀进, 刘景华, 吴镒潾, 毛煜, 李绍滋. 由粗到细的分层特征选择[J]. 电子学报, 2022, 50(11): 2778-2789.
[13]	汪成亮, 赵凯, 刘嘉敏. 智能环境下基于边缘设备规则推理的数据预部署研究[J]. 电子学报, 2022, 50(10): 2347-2360.
[14]	高雷阜, 张梦瑶, 赵世杰. 融合簇边界移动与自适应合成的混合采样算法[J]. 电子学报, 2022, 50(10): 2517-2529.
[15]	李青青, 马慧芳, 李举, 李志欣, 姜彦斌. 属性网络中结合用户偏好的社区搜索和离群点检测[J]. 电子学报, 2022, 50(9): 2172-2180.