【作者】 唐德玉；

【导师】 董守斌；

【作者基本信息】 华南理工大学 ， 计算机应用技术， 2015， 博士

【摘要】 群智能是一种启发式优化算法,是通过模拟大自然中各种物种(比如生物、昆虫或动物等)的觅食等行为,利用群体中个体间的互动,实现了最优化目标的求解。现实生活中,很多实际问题都是最优化问题,比如图像分割问题、基因聚类问题、社会网络聚类问题、医疗诊断中的分类和预测问题、经济派遣问题、护士排班问题、车辆路径问题等,而群智能算法在解决这些问题上,表现出良好的性能,并已经成为目前研究的一个热点。然而,还有很多问题亟待解决,比如算法寻优的速度,寻优的精度等。而且,理论上已经证明,任何一个群智能算法都不能解决所有优化问题。模因论(memetic)是受达尔文自然进化原则及道金斯的文化进化概念启发的计算智能领域。模因可以被理解为‘文化基因’,与基因不同的是,文化基因有继承和传播的特征。模因论使用复杂的结构,比如简单个体的组合及模因(memes)来解决问题。模因计算(Memetic Computing)的全局搜索和局部搜索的结合机制使其搜索效率在某些问题领域比传统的一些智能算法快几个数量级,可应用于广泛的优化问题领域并得到满意的结果。模因计算提出的是一种框架、是一个概念,在这个框架下,采用不同的搜索策略可以构造不同的群智能算法。对此,本文的研究重点是深入研究模因计算框架下的群智能优化算法的思想及理论,对肿瘤生长机制及数学模型做深入研究和探索,受此启发,以模因计算框架为基础,提出新的群智能算法---入侵肿瘤生长优化算法(ITGO),并将其应用到聚类问题及支持向量机优化问题中。本文主要围绕模因计算框架下群智能算法的改进及肿瘤生长理论和方法而展开研究,并完成了以下主要工作内容和创新点:1)在模因计算框架下,由于传统量子粒子群算法只考虑了局部搜索能力,降低了算法的寻优的精度,特别是,在解决大规模优化问题上,性能明显下降。对此,我们首先对传统的局部搜索策略进行了改进,采用新的加权方法,加强局部搜索能力。在此基础上,为了加强算法的全局搜索能力,研究模因算法的规律,并假设粒子(鸟)中有“鸟王”的存在,并对此建立有记忆的数学模型。记忆反映了模因继承的特征。而有记忆规则可以增加算法的多样性,使得算法不易陷入局部最优。最后,我们提出结合模因算法的有记忆的量子粒子算法(SMQPSO)。优化实验结果表明,模因计算框架下的量子粒子群算法,在解决大规模优化问题上,表现出较好的性能。2)混合蛙跳算法(SFLA)是典型的模因计算框架下的群智能优化算法。其局部搜索采纳了简化的粒子群搜索规则,而模因混洗策略加强了其全局搜索能力。但简化的粒子群搜索规则收敛速度较慢,精度也不高。另外,在青蛙搜索过程中,经常发生青蛙越界的问题。对此,在局部搜索策略上,本文引入重心吸引因子,以提高青蛙探索能力;采纳空间缩放的方法解决青蛙越界问题,提出有重心的空间缩放混合蛙跳算法(sg SFLA)。优化实验证明,改进的算法既解决了青蛙越界问题,也提高了算法的性能。3)在模因计算框架下,传统教与学优化算法选择了较好的局部搜索策略,而忽略了全局搜索能力。只考虑了模因的继承特征而没有考虑模因的传递特征。具体表现为,算法只考虑一个班的情况,而且学生之间互动学习过程中,没有考虑教师的引导作用,从而降低了算法解决多模优化问题的精度。对此,本文使用模因混洗策略,提出多班的教与学优化算法(CTLBO)。实验结果表明,由于新的框架增加了算法的多样性,使得算法在解决多模优化问题上,表现出较好的性能。4)通过对量子粒子群算法、混合蛙跳算法及教与学优化算法机制的深入研究,掌握了模因计算框架下群智能算法设计的基本原则。通过对入侵肿瘤生长机制及数学模型的深入研究,受人类大脑中肿瘤生长及入侵行为的启发,提出入侵肿瘤生长优化算法(ITGO)。在模因计算框架下,脑瘤中的细胞可分为入侵细胞群、增殖细胞群、休眠细胞群和快死的细胞群,不同子群的互换机制,保证算法的全局搜索能力。局部搜索能力,表现在不同细胞子群自身的搜索规则,这可以保证算法的搜索速度。为了模拟肿瘤生长机制,我们假设,增殖细胞的入侵行为符合levy分布的;休眠细胞的生长是通过增殖细胞引导及休眠细胞之间的互动完成的;而快死了的细胞的生长是受增殖细胞和休眠细胞的引导而完成的,并且他们有可能死亡。最后,实验结果表明了入侵肿瘤生长优化算法的性能。5)使用入侵肿瘤生长优化算法(ITGO)解决聚类问题及支持向量机优化问题。聚类问题往往被看做为一种多模的连续优化问题,理论已经证明,其为NP问题。对聚类中心进行编码,目标是实现类内样本距离最近,而类与类之间距离最远。实验结果表明,本文提出的算法降低了聚类的错误率。而支持向量机(SVM)是机器学习中十分重要的一个算法。由于其较好的性能而被广泛使用。但其性能受到其参数的影响,其参数优化问题,成为使用支持向量机的关键问题。对此,我们使用入侵肿瘤生长优化算法来解决这个问题,实验结果表明,本文提出的算法提高了算法分类的准确率。以上工作都是围绕模因计算框架下的群智能算法及入侵肿瘤生长理论和方法的研究而展开,不仅涉及模因论、物理理论、统计方法及入侵肿瘤生长理论而且也有数据挖掘、机器学习方面的理论实践,体现了对群智能算法研究的深度和系统性。本文研究成果有助于人们进一步研究模因计算框架下的其他群智能算法的理论和方法,并将本文提出的算法推广到更多领域,解决现实中更多复杂的优化问题。更多还原

【Abstract】 Swarm intelligence is a kind of heuristic optimization algorithm,which simulates the foraging behavior of species in nature(such as animals or insects) etc.) by the interaction between individuals, to achieve the optimal solution of s the target. In real life, many practical problems are optimization problems, such as image segmentation, genetic clustering problem, social network clustering problem, classification and prediction of medical diagnosis problems, the economic dispatch problem, nurse scheduling problem, vehicle routing problem etc. and swarm intelligence algorithms show good performance in solving these problems, and has become a research hotspot in recent years. However, there are many problems to be solved, such as the speed of algorithm optimization, the accuracy of optimization etc.. Moreover, it has been proved theoretically that only one swarm intelligence algorithm can not solve all the problem.Memetic is a field of intelligent computation inspired by the concept of natural evolution principle of Darwin and the cultural evolution principle of Dawkins. Meme can be understood as a’ culture gene’, different from the gene, the culture gene has the characteristics of the inheritance and propagation. Memetic uses the complex structures, such as the simple combination of individual and meme to solve the problem. Memetic computing combines with the mechanism of the global search and local search,which makes the better search efficiency in some areas than some traditional intelligent algorithm, it is faster in several orders of magnitude. It can be applied to the field of a wide range of optimization problems and abtains satisfactory results. Memetic computing provides a framework or a concept, in this framework, using different search strategies, peoples can establish new swarm intelligence algorithm.In this regard, the focus of this paper is to study the thought and theory of the swarm intelligence optimization algorithm, under the framework of the memetic calculation. Studys the mechanism and mathematical model of tumor growth, inspired by this,under the memetic computing framework, put forward a new swarm intelligence algorithm, named the’ invasion tumor growth algorithm’, and apply it to the clustering problem and the support vector machine optimization problems.This paper mainly focuses on the improvement of swarm intelligence algorithm under the framework of memetic computing, and the theory and methods of tumor growth, and completed the following main contents and innovation points:1) In the framework of memetic computing, because the traditional quantum behaved particle swarm optimization algorithm only considers the local search ability, reduces the accuracy of optimization, especially, for the large-scale optimization problems, the performance was significantly decreased. In this regard, we first improves the traditional local search strategy, using the weighted method, strengthens the ability of local search. On this basis, in order to strengthen the global search ability of the algorithm, research the rules of memetic algorithms, assuming that, there is a ‘bird kingdom’ in the the particles(birds), and has established the mathematical model with memory. Memory reflects the meme inherited characteristics. While the memory rules can increase the diversity of the algorithm, so the algorithm is not easy to fall into local optimal. Finally, we proposed the memtic quantum particle algorithm with memory(SMQPSO). The experimental results show that quantum behaved particle swarm optimization algorithm under the framework of memetic computing has a good performance to solve the large-scale optimization problems.2) Shuffled frog leaping algorithm(SFLA) is a typical swarm intelligence optimization algorithm under the framework of memetic computing. The local search is adopted like the simplified search rules of particle swarm, while meme shuffled strategy strengthens its global search ability. But the simplified search rules of the particle swarm has the slow convergence speed and the precision is not better. In addition, in the search process, the frog jump out of bounds often happen. In this regard, the local search strategy is introduced by the focus attracting factor in this paper, in order to improve the exploring ability of the frog; using the spatial zoom method to solve border problems, put forward the spatial zoom shuffled frog leaping algorithm(sg SFLA) with the attracting factor. Experimental results show that the improved algorithm can only solve the frog cross-border problems, but also improve the performance of the algorithm.3) In the framework of memetic computing, traditional teaching and learning optimization algorithm select the better local search strategy, while ignoring the global search ability. Only consider the characteristics of inheritance without considering the characteristics of transmission of meme. Specifically, the algorithm only considers one class, and in the interactive learning process of the students, the guiding role of teachers is not considered, so reduce the precision of the algorithm to solve multimodal optimization problems. In this regard, use the memtic shuffle strategy, put forward a new teaching and learning optimization algorithm with many classes(CTLBO). Experimental results show that under the new framework, the algorithnm increases the diversity, to solve multimodal optimization problems, it has a good performance.4) Based on the deeply rearch of the quantum particle swarm algorithm, shuffled frog leaping algorithm and teaching and leaning optimization algorithnm, grasp the basic principle of the intelligent algorithm under the memetic computing framework. Through the deep research on the growth mechanism and mathematical model of the invasion of tumor growth, inspired by the invasive behavior of the human brain, putford the invasive tumor growth optimization algorithm(ITGO).In the framework of memetic computing, the cells of tumor can be divided into invasive cells, proliferative cells, resting cells and dying cells, the exchange mechanism in different subgroups guarantee the global search ability of the algorithm. The local search ability presents the different cell subgroup’s own search rules, which can guarantee the speed of convergence of the algorithm. In order to simulate tumor growth mechanism, we assume that the intrusion of proliferating cells grow according with Levy distribution; resting cell grows by the leading of proliferative cell and the interaction between resting cells c; and dying cell growth is leaded by the proliferative cell and resting cells,or they may be killed. Finally, the experimental results show that the performance of the invasive tumor growth optimization algorithm.5) Using the invasive tumor growth(ITGO) optimization algorithm to solve the clustering problem and support vector machine optimization problem. The clustering problem is often viewed as a continuous multimode optimization problem, theory has proved that it is the NP problem. Encodes the cluster centers, the goal is to achieve the near distance within class and the farthest distance in different classes. The experimental results show that the algorithm proposed in this paper reduces the clustering error rate. Support vector machine(SVM) is a machine learning algorithm, because of its good performance and widely used. But its performance is influenced by the parameters, the parameter optimization problem has become the key problem of support vector machine. In this regard, we use the invasive tumor growth optimization algorithm to solve this problem. The experimental results show that the proposed algorithm improves the accuracy of classification.All of the above work is around the research of swarm intelligence algorithm under the memetic computing framework and the theory and method of invasive tumor growth, not only relates to the memtic theory, physics, statistics method and the theory of invasive tumor growth but also in theory and practice of data mining and machine learning, reflects the depth and systematic for the research of the intelligence algorithm. This research is helpful to further study of other methods of swarm intelligence algorithm under memetic computing framework, and this algorithm can be extended to more areas, to solve the more complicated optimization problem in reality.更多还原