Page 367 - 《软件学报》2024年第4期
P. 367
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2024,35(4):1945−1963 [doi: 10.13328/j.cnki.jos.006843] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
*
基于遗传算法的划分序乘积空间问题求解层选择
徐 怡 1,2 , 邱紫恒 1
1
(安徽大学 计算机科学与技术学院, 安徽 合肥 230601)
2
(计算智能与信号处理教育部重点实验室 (安徽大学), 安徽 合肥 230601)
通信作者: 徐怡, E-mail: 08055@ahu.edu.cn
摘 要: 划分序乘积空间作为一种新的粒计算模型, 可以从多个视角和多个层次对问题进行描述和求解. 其解空间
是由多个问题求解层组成的格结构, 其中每个问题求解层由多个单层次视角构成. 如何在划分序乘积空间中选择
问题求解层是一个 NP 难问题. 为此, 提出一种两阶段自适应遗传算法 TSAGA (two stage adaptive genetic algorithm)
来寻找问题求解层. 首先, 采用实数编码对问题求解层进行编码, 然后根据问题求解层的分类精度和粒度定义适应
度函数. 算法第 1 阶段基于经典遗传算法, 预选出一些优秀问题求解层作为第 2 阶段初始种群的一部分, 从而优化
解空间. 算法第 2 阶段, 提出随当前种群进化迭代次数动态变化的自适应选择算子、自适应交叉算子以及自适应
大变异算子, 从而在优化的解空间中进一步选择问题求解层. 实验结果证明了所提方法的有效性.
关键词: 粒计算; 划分序乘积空间; 遗传算法; 问题求解层
中图法分类号: TP18
中文引用格式: 徐怡, 邱紫恒. 基于遗传算法的划分序乘积空间问题求解层选择. 软件学报, 2024, 35(4): 1945–1963. http://www.jos.
org.cn/1000-9825/6843.htm
英文引用格式: Xu Y, Qiu ZH. Problem Solving Level Selection in Partition Order Product Space Based on Genetic Algorithm. Ruan
Jian Xue Bao/Journal of Software, 2024, 35(4): 1945–1963 (in Chinese). http://www.jos.org.cn/1000-9825/6843.htm
Problem Solving Level Selection in Partition Order Product Space Based on Genetic Algorithm
1,2
XU Yi , QIU Zi-Heng 1
1
(School of Computer Science and Technology, Anhui University, Hefei 230601, China)
2
(Key Laboratory of Intelligent Computing and Signal Processing (Anhui University), Ministry of Education, Hefei 230601, China)
Abstract: As a new granular computing model, partition order product space can describe and solve problems from multiple views and
levels. Its problem solving space is a lattice structure composed of multiple problem solving levels, and each problem solving level is
composed of multiple one-level views. How to choose the problem solving level in the partition order product space is an NP-hard
problem. Therefore, this study proposes a two-stage adaptive genetic algorithm (TSAGA) to find the problem solving level. First, real
encoding is used to encode the problem solving level, and then the fitness function is defined according to the classification accuracy and
granularity of the problem solving level. The first stage of the algorithm is based on a classical genetic algorithm, and some excellent
problem solving levels are pre-selected as part of the initial population of the second stage, so as to optimize the problem solving space.
In the second stage of the algorithm, an adaptive selection operator, adaptive crossover operator, and adaptive large-mutation operator are
proposed, which can dynamically change with the number of iterations of the current population evolution, so as to further select the
problem solving level in the optimized problem solving space. Experimental results demonstrate the effectiveness of the proposed method.
Key words: granular computing; partition order product space; genetic algorithm; problem solving level
粒计算 (granular computing) 是当前智能计算领域中模拟人类思维解决复杂问题的新方法 [1,2] . 粒结构是粒计
算的基础, 人们通过粒结构对复杂问题进行理解和描述, 然后基于粒结构对问题进行求解. 粒结构的两个基本原则
* 基金项目: 国家自然科学基金 (62076002); 安徽省自然科学基金 (2008085MF194)
收稿时间: 2022-04-30; 修改时间: 2022-07-18, 2022-09-20; 采用时间: 2022-12-02; jos 在线出版时间: 2023-07-28
CNKI 网络首发时间: 2023-07-31
