【作者】 刘明姬；

【导师】 吕显瑞；

【作者基本信息】 吉林大学 ， 运筹学与控制论， 2004， 硕士

【摘要】 遗传算法是一种借鉴生物界自然选择和进化机制发展起来的高度并行的随机自适应搜索算法，是由美国的Holland教授首次提出的。近年来众多研究者不断的对其进行改进和发展，并将其广泛应用于那些难以用传统方法进行求解的复杂问题，如组合优化、模式识别、图像处理、数值优化等。 遗传算法采用简单的编码来表示各种不同问题的复杂结构，对解群体的选择、交叉、变异等遗传操作不依赖于所解的问题，而是简单的按照优胜劣汰的自然选择规律确定搜索方向，是一种有向的随机搜索。从而特别适用于大规模并行处理，具有不受搜索空间条件(如可微、单峰、连续等)的约束及不需要其它辅助信息的特点。这些特点使得遗传算法不仅能获得较高的效率，而且具有简单性，易操作性，全局最优性，隐并行性，鲁棒性及通用性。但是它也存在着收敛速度慢，收敛过程中稳定性差，可控性差和早熟收敛等缺陷。 基于遗传算法的机器学习是将遗传算法与机器学习系统相结合的产物，是当前遗传算法研究的一个重要方面。其中最引人注目的是对分类器系统的研究。竞争的信度分配和以遗传算法为核心的规则发现构成了基于分类器的遗传机器学习系统。1986年Holland等实现了第一个基于遗传算法和桶队列算法反馈机制的分类器系统。 本文将遗传算法与机器学习基本思想相结合，在分类器学习系统的基础上，对遗传机器学习系统进行了一些重要的局部改进，提出改进的遗传机器学习系统。 (1) 增强因子的引入。在信度分配中，对获胜分类器进行奖励，保证了最优个体的存在性，增强了算法的局部搜索能力，使种群向着最优解不断进化. (2)排挤因子的引入.在规则与消息系统和遗传算法过程中均引入了排挤因子.每次机器学习后用最优环境消息替换规则集中最差个体;每次遗传算法后，用交叉操作产生的较优子代替换原种群中与其最相似的最差个体. 排挤因子的引入解决了选择压力与种群多样性的矛盾，不但保证了最优个体的存在性，还没有破坏种群的多样性. (3)合并因子的引入.每次遗传机器学习后对相似分类器进行合并，最终权值取所有相似分类器的平均值.这样防止超级个体的产生，避免了搜索带逐渐变窄而产生的过早收敛，并维持了原来的算法搜索空间. (4)改进系统中对于信度分配的具体计算: 假定一个分类器c在t时刻的权值为S(c，约，投标系数为几记，有效投标中随机噪声为N(a。、)，投标税系数为几idta二，存活税系数为q价。二，进行投标未进行投标 1上n︶了!l，、esesL投标控制参数b’二旧优胜者为?n，新胜者为m+1，对优胜者的奖励为侧，收入为州约，且州约二及《二，t) 那么我们就能够得到 分类器C的投标值为B乞d(C，t)=e。:以·S(C，亡)有效投标值为EB:己=B:d+N(a。、。)税值为Tax=Cl:了。乙a二·S+几:己亡a二·b‘·S候选分类器C参加投标一条消息后，它的权值为S(C，t+l)=S(C，亡)一B乞d(C，t)一T(C，t)+R(亡)有效投标最大者为当前优胜者，其权值为S(。+l，亡+1)=S(。+l，亡)一B:d(m+1，亡)一T(m+1，t)+R(艺)+R‘ 定理1.1当分类器的回报趋于稳定时，投标值接近于回报值. 定理表明在分类器系统中，规则的权值是否处于稳定状态，对遗传算法的学习过程很大影响. 经实践我们发现如此将遗传算法与机器学习相结合是非常有效的.机器学习对一些函数关系很明确的数据收敛速度很快，而对于一些函数关系不是很确定的例子来说其表现就不是很理想了，机器学习会产出摆动，不够精确，甚至陷入局部极小;而此时遗传算法就会表现出其优势，遗传算法根据要求建立一个规则重组机制，并且根据这个机制来对规则进行重组，产生新的，可能性能更好的规则，并淘汰不好的规则，跳出局部极小的圈子，扩大搜索范围，加速向最优解逼近.这样两种保证收敛的算法相结合，更加保证了整个算法的收敛性，加速算法收敛速度，是很有效的组合. 对于本改进的遗传机器学习系统，将遗传算法与机器学习有效的结合起来，并辅以改进因子，令二者交替进行，在程序运行的前期，由于要求的相似度较低，分类器投标活跃，机器学习占主导地位;而在后期，机器学习到了一定程度，遗传算法就相应的占了主导.这样更加保证了算法的稳定性，收敛性，全局搜索性，克服了非成熟收敛等弊病.改进算法不要求所要解决问题目标函数的连续性，凸性，光滑性等，特别适用于维数高，总体大，环境复杂，问题结构不十分清楚的情况. 最后我仃J将改进的遗传机器学习系统应用于模式识别和多目标优化问题，分别针对疾病的诊断模型和投资的收益与风险模型，给出了具体的算例. (一)改进的遗传机器学习系统在模式识别中的应用. 改进的遗传机器学习系统具有强大的学习功能，是解决模式识别问题的有效工具.用它来解决医学诊断中的数据优化问题一一用最少的诊断数据得出较为正确的结论，使医学诊断能够更加科学、经济和便捷. 这里以乳腺癌病例诊断为例，由病人的表征输入，产生最可能的疾病状态，实现自动医学诊断. 我们依据已确诊病例信息的编?更多还原

【Abstract】 Genetic Algotithm is a kind of highly parallel adaptive random search method which is advanced by professor. Hollad originally. It is based on the biological nature selection and evolutionism together. In recent years people are continuing to improve and develope it, applying it into such complex problems which couldn’t be solved in the traditional methods, e.g. advantageous making-up combinatorial optimization, image processing and numerical value optimization. Now it has become a heated topic.Genetic Algorithm uses the simple codes to express different complex structures of questions, the selection, crossover and mutation operators to the population are not dependent on the question, while denning the searhing direction according to the natural selecting rule of survical of the fittest simply. This is a sort of directed random selection. Therefore this way is suitable to large par-ellel dealing. It is unbound of the condition of searching space differentiability, single-peak, continuity and there is no need of other assistant instrument. These features not only make the genetic algorithm become higher efficient and easy to operate, but aslo make it possess global optimality., implicit parallelism, robustness and general. This method also has some defects, e.g. the slow speed of convergence, the badness of stability and operation, premature convergence.Genetics Based Machine Learning is one important aspect of current ge-netic algorithm research. The most outstanding study is the research of classifier system. The genetic machine learning system based on classifier system is composed of credit assignment algorithm, the rule and message system and genetic algorithm. Holland presented the first classifier system which is centered on the genetic and the bucket brigade algorithm in 1986.This article combines the ideas between genetic algorithm and machine learning, gives some important improvements on the classifier system and puts forward the improved genetic algorithm based on machine learning.(1) The application of strengthening factor.In the credit assignment, the reward to the winning classifier ensures the existence of the best individual and strengthens local searching ability of this algorithm, making the population approach the most excellent solution continuously.(2) The application of crowding factor.We use the crowding factor both in the rule and message system and the process of the genetic algorithm. We replace the worst classifiers with the best conditional messages after each machine learning; in addition, we take the place of the worst individual in the original group with the most similar better one of the filial generation produced by the crossover operator after each genetic algorithm.The introduction of crowding factor solves the contradiction between the selection pressure and the population diversity. It not only ensures the existence of the best individual, but also keeps the population diversity.(3) The application of combine factor.We combine similiar classifiers after each algorithm perfoment and make the average value of all similiar classifiers as the final strength value. This way prevents the appearance of super individual and avoids premature convergence be-cause of the gradual narrowing of searching strap, maintaining the former searching space.(4) The calculation of the credit assignment in improved genetic algorithm based on machine learning.Let the strengh of classifier C in time t be S(C, t) , the bid coefficient be Cbid, the random noise in the valid bid be N(bid), the bid tax coefficient be Cbidtax, the life tax coefficient be Clifetax, the bid control parameter be1, when it bidthe old winner be m, the new one be m + 1,0, when it dosen’t bid , the reward to the winner be R’, the repay be R(t), and R(t) = Bid(m,t).When C becomeing the candidate, the bid value is The valid bid isEBid = Bid + N( bid)The tax isWhen the candidate classifier C takes part in biding a message, its strengh isStrength(C, t + 1) = Strength(C, t) - Bid(C,更多还原