Interactive Genetic Algorithm Based on Collective Decision Making with Multi-user Collaboration
-
摘要: 采用交互式遗传算法求解大数据信息检索问题时，为实现偏好信息的提取和优化，单用户需完成较多数量的人-机交互操作，由此易产生用户疲劳、算法搜索效率低的难题。对此，该文在算法中引入多用户并行策略，通过群体决策优势，提高样本利用效率。首先，根据优化目标性质确定共性化协同或个性化协同类型，基于用户浏览行为计算用户相似度和个体相似度。然后，通过共享偏好相似用户的偏好相似个体预测个体区间适应值。基于个体表现型相似度聚类，提出大规模种群个体“区间数-区间数”适应值赋值策略。最后，依据子代种群个体与父代种群最优个体的相似性，推荐用户最佳评价个体。将所提方法应用于装饰性墙壁纸选型问题，并与已有典型方法比较。结果表明，所提方法在推荐个体质量、减轻用户疲劳、提高搜索效率等方面均具有优越性。Abstract: When using interactive genetic algorithm to solve big data information retrieval problem, single user needs to complete more human-machine interactive operation to achieve preference information extraction and optimization, thus it is easy to generate the problem of user fatigue and algorithm low efficiency. A multi-user strategy is introduced by making full use of the advantages of group decision to improve the sample utilization efficiency. First of all, multi-user collaborative type is devided into common collaboration or personalized collaboration according to the optimization goal which calculats user similarity and individual similarity based on user’s browsing behaviors. Then, individuals’ interval fitness is forecasted by sharing similar individual of similarity users. Based on phenotype similarity clustering, the large scale population individuals of " interval-interval” fitness assignment strategy is introduced. Finally, the best evaluation individual is recommended according to the similarities between offspring individuals and parent individuals. The proposed method is applied to decorative wallpaper design problem and is compared with existing typical methods. The experimental results confirm that the proposed algorithm has advantages in improving optimization quality and alleviating user fatigue while improving its efficiency in exploration.
-
Key words:
- Genetic algorithms /
- Interaction /
- Collective decision making /
- Multi-user /
- Collaboration
-
表 1 共性化协同结果
共性化协同次数 属性标准差 ${\omega _\gamma }$ 偏好相似个体数 ${N_m}$ 协同用户数k 协同耗时(s) 个体相似度 $\mu ({x_i},{x_B})$均值 ${x_{i1}}$ ${x_{i2}}$ ${x_{i3}}$ ${x_{i4}}$ ${x_{i5}}$ 1 1.43 0.65 0.54 0.69 1.73 24 4 53 0.63 2 1.38 0.41 0.43 0.37 1.52 35 9 67 0.78 3 1.24 0.22 0.24 0.32 1.38 48 13 109 0.86 
下载: 导出CSV
表 2 用户相似度与个体相似度结果
算法 用户相似度 $M({u_a},{u_b})$均值 个体相似度 $\mu ({x_i},{x_B})$均值 第1次 第2次 第3次 第1次 第2次 第3次 本文算法 0.41 0.48 0.53 0.63 0.78 0.86 MiGA 0.36 0.42 0.47 0.54 0.66 0.73 GS-IGA 0.32 0.39 0.45 0.48 0.59 0.68
下载: 导出CSV
表 3 算法优化解数目和成功率
算法 项目1 项目2 完全匹配解用户 不满意度DI均值 进化耗时(s) 相同解用户 不满意度DI均值 进化耗时(s) 本文算法 3 0.14 347 2 0.17 392 MiGA 2 0.21 438 0 0.26 492 GS-IGA 1 0.37 503 0 0.32 533
下载: 导出CSV
表 4 优化结果形态分组
算法 优化结果属性分组/代表性个体 分组1 分组2 分组3 分组4 分组5 本文算法 (6, 190, 245, 34, 25) (6, 185, 220, 27, 25) (6, 202, 250, 27, 22) (6, 197, 230, 25, 17) $ \times $ MiGA (6, 241, 227, 38, 45) – (7, 145, 237, 36, 26) – (6, 188, 207, 29, 38) GS-IGA – (6, 190, 229, 37, 43) – $ \times $ $ \times $
下载: 导出CSV
-
李清霞, 魏文红, 蔡昭权. 混合用户和项目协同过滤的电子商务个性化推荐算法[J]. 中山大学学报(自然科学版), 2016, 55(5): 37–42 doi: 10.13471/j.cnki.acta.snus.2016.05.007LI Qingxia, WEI Wenhong, and CAI Zhaoquan. Hybrid user and item based collaborative filtering personalized recommendation algorithm in E-commerce[J]. ACTA Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(5): 37–42 doi: 10.13471/j.cnki.acta.snus.2016.05.007 王占, 林岩. 基于信任与用户兴趣变化的协同过滤方法研究[J]. 情报学报, 2017, 36(2): 197–205 doi: 10.3772/j.issn.1000-0135.2017.02.010WANG Zhan and LIN Yan. Research on collaborative filtering method based on trust and the change of user’s interest[J]. Journal of the China Society for Scientific and Technical Information, 2017, 36(2): 197–205 doi: 10.3772/j.issn.1000-0135.2017.02.010 潘涛涛, 朱珂, 吴毅涛. 基于满意区间的协同过滤推荐算法[J]. 计算机应用研究, 2017, 34(8): 2282–2286 doi: 10.3969/j.issn.1001-3695.2017.08.009PAN Taotao, ZHU Ke, and WU Yitao. Satisfactory intervals similarity-based collaborative filtering recommendation algorithm[J]. Application Research of Computers, 2017, 34(8): 2282–2286 doi: 10.3969/j.issn.1001-3695.2017.08.009 ALJAWAWDEH H J, SIMONS C L, and ODEH M. Metaheuristic design pattern: preference[C]. Proceedings of the Companion Publication of the Annual Conference on Genetic and Evolutionary Computation, Madrid, 2015: 1257–1260. 郭一楠, 巩敦卫, 周勇. 基于多智能体系统的协同交互式进化计算模型[J]. 系统仿真学报, 2005, 17(7): 1548–1552 doi: 10.3969/j.issn.1004-731X.2005.07.005GUO Yinan, GONG Dunwei, and ZHOU Yong. Cooperative interactive evolutionary computation model based on multi-agent system[J]. Journal of System Simulation, 2005, 17(7): 1548–1552 doi: 10.3969/j.issn.1004-731X.2005.07.005 QUIROZ C, LOUIS J, and BANERJEE A. Towards creative design using collaborative interactive genetic algorithm[C]. Proceedings of the Eleventh Conference on Congress on Evolutionary Computation, Trondheim, 2009: 1849–1856. SAYAMA H and DIONNE S D. Studying collective human decision making and creativity with evolutionary computation[J]. Artificial Life, 2015, 21(3): 379–393 doi: 10.1162/ARTL_a_00178 SUN Xiaoyan, YANG Lei, and GONG Dunwei. Interactive genetic algorithm assisted with collective intelligence from group decision making[C]. IEEE Congress on Evolutionary Computation, Brisbane, 2012: 1–8. GONG Dunwei, YANG Lei, and SUN Xiaoyan. Applying knowledge of users with similar preference to construct surrogate models of IGA[J]. Chinese Journal of Electronics, 2015, 24(3): 555–563 doi: 10.1049/cje.2015.07.020 SEYAMA T and MUNETOMO M. Development of a multi-player interactive genetic algorithm-based 3D modeling system for glasses[C]. IEEE Congress on Evolutionary Computation, Vancouver, 2016: 846–852. GONG Dunwei, SUN Jing, and MIAO Zhuang. A set-based genetic algorithm for interval many-objective optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(1): 47–60 doi: 10.1109/TEVC.2016.2634625 巩敦卫, 陈健. 基于精英集选择进化个体的交互式遗传算法[J]. 电子学报, 2014, 42(8): 1538–1544 doi: 10.3969/j.issn.0372-2112.2014.08.012GONG Dunwei and CHEN Jian. Interactive genetic algorithms with selecting individuals using elite set[J]. Acta Electronica Sinica, 2014, 42(8): 1538–1544 doi: 10.3969/j.issn.0372-2112.2014.08.012 XUAN Jifeng, HE Jiang, REN Zhilei, et al. Solving the large scale next release problem with a backbone based multilevel algorithm[J]. IEEE Transactions on Software Engineering, 2012, 38(5): 1195–1212 doi: 10.1109/TSE.2011.92 巩敦卫, 陈健, 孙晓燕. 新的基于相似度估计个体适应值的交互式遗传算法[J]. 控制理论与应用, 2013, 30(5): 558–566 doi: 10.7641/CTA.2013.21164GONG Dunwei, CHEN Jian, and SUN Xiaoyan. Novel interactive genetic algorithm for estimating individual fitness based on similarity[J]. Control Theory&Applications, 2013, 30(5): 558–566 doi: 10.7641/CTA.2013.21164 ALLYSSON A A, MATHEUS P, and ITALO Y. An architecture based on interactive optimization and machine learning applied to the next release problem[J]. Automated Software Engineering, 2017, 24(3): 623–649 doi: 10.1007/s10515-016-0200-3 KUZMAL M and ANDREJKOV G. Predicting user’s preferences using neural networks and psychology models[J]. Applied Intelligence, 2016, 44(3): 526–538 doi: 10.1007/s10489-015-0717-3 毛宜钰, 刘建勋, 胡蓉, 等. 基于Logistic函数和用户聚类的协同过滤算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1252–1258 doi: 10.3785/j.issn.1008-973X.2017.06.024MAO Yiyu, LIU Jianxun, HU Rong, et al. Collaborative filtering algorithm based on logistic function and user clustering[J]. Journal of Zhejiang University(Engineering Science.) , 2017, 51(6): 1252–1258 doi: 10.3785/j.issn.1008-973X.2017.06.024 赵文涛, 成亚飞, 王春春. 基于Logistic 时间函数和用户特征的协同过滤算法[J]. 计算机应用与软件, 2017, 34(2): 285–289 doi: 10.3969/j.issn.1000-386x.2017.02.051ZHAO Wentao, CHENG Yafei, and WANG Chunchun. Collaborative filtering algorithm based on Logistic time function and user features[J]. Computer Applications and Software, 2017, 34(2): 285–289 doi: 10.3969/j.issn.1000-386x.2017.02.051 -
图(4) / 表(4)
计量
- 文章访问数: 1929
- HTML全文浏览量: 502
- PDF下载量: 48
- 被引次数: 0
下载:
