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

• 学术论文 • 上一篇    下一篇

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

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

  1. 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 Rui1,2, DONG Hong-bin1, XING Wei1, LIU Wen-jie1, KONG Fei1   

  1. 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:

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

中图分类号: