yj1.m ：简单一元函数优化实例，利用遗传算法计算下面函数的最大值 0.2)*10sin()(+=x x x f π，∈x [-1, 2] 选择二进制编码，种群中个体数目为40，每个种群的长度为20，使用代沟为0.9， 最大遗传代数为25 译码矩阵结构：?????????? ??????? ???? ?=ubin lbin scale code ub lb len FieldD 译码矩阵说明： len – 包含在Chrom 中的每个子串的长度，注意sum(len)=length(Chrom)； lb 、ub – 行向量，分别指明每个变量使用的上界和下界； code – 二进制行向量，指明子串是怎样编码的，code(i)=1为标准二进制编码， code(i)=0则为格雷编码； scale – 二进制行向量，指明每个子串是否使用对数或算术刻度，scale(i)=0为算术 刻度，scale(i)=1则为对数刻度； lbin 、ubin – 二进制行向量，指明表示范围中是否包含每个边界，选择lbin=0或 ubin=0，表示从范围中去掉边界；lbin=1或ubin=1则表示范围中包含边界； 注：增加第22行：variable=bs2rv(Chrom, FieldD);否则提示第26行plot(variable(I), Y, 'bo'); 中variable(I)越界 yj2.m ：目标函数是De Jong 函数，是一个连续、凸起的单峰函数，它的M 文件objfun1包含在GA 工具箱软件中，De Jong 函数的表达式为： ∑ == n i i x x f 1 2 )(， 512512≤≤-i x 这里n 是定义问题维数的一个值，本例中选取n=20，求解 )(min x f ，程序主要变量： NIND （个体的数量）：＝40； MAXGEN （最大遗传代数）：=500； NV AR （变量维数）：=20； PRECI （每个变量使用多少位来表示）：=20； GGAP （代沟）：=0.9 注：函数objfun1.m 中switch 改为switch1，否则提示出错，因为switch 为matlab 保留字，下同！ yj3.m ：多元多峰函数的优化实例，Shubert 函数表达式如下，求)(min x f 【shubert.m 】
基于遗传算法的一种新的约束处理方法 苏勇彦1，王攀1，范衠2 （1武汉理工大学 自动化学院， 湖北 武汉 430070） （2丹麦理工大学 机械系 哥本哈根） 摘 要：本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。 关键词：遗传算法、约束处理、可行解、不可行解、两种群混合交叉 1引言 科学研究和工程应用中许多问题都可以转化为求解一个带约束条件的函数优化问题[1]。遗传算法（Genetic Algorithm ）与许多基于梯度的算法比较,具有不需要目标函数和约束条件可微,且能收敛到全局最优解的优点 [2]，因此，它成为一种约束优化问题求解的有力工具。目前，基于GA 的约束处理方法有拒绝策略，修复策略，改进遗传算子策略以及惩罚函数策略等。但是这些方法都存在一些问题[3]：修复策略对问题本身的依赖性，对于每个问题必须设计专门的修复程序。改进遗传算子策略则需要设计针对问题的表达方式以及专门的遗传算子来维持解的可行性。惩罚策略解的质量严重依赖于惩罚因子的选取，当惩罚因子不适当时，算法可能收敛于不可行解。 本文针对目前的约束处理方法中存在的问题，提出一种新的约束处理方法。该方法通过可行解和不可行解混合交叉的方法对问题的解空间进行搜索，对可行种群和不可行种群分别进行选择操作。避免了惩罚策略中选取惩罚因子的困难，使得约束处理问题简单化。实例测试结果表明，该约束处理方法的有效性。 2约束处理方法描述 2.1单目标有约束优化问题一般形式 )(max x f ..t s ;0)(≤x g i 1,,2,1m i L L =;0)(=x h i )(,,1211m m m m i +=+=L X x ∈ 这里都是定义在m m m m h h h g g g f ,,,;,,;2121111L L ++n E 上的实值函数。X 是n E 上的 子集，x 是维实向量，其分量为。上述问题要求在变量满足约 束的同时极大化函数。函数通常为目标函数。约束n n x x x ,,,21L n x x x ,,,21L f f ;0)(≤x g i 称为不等式约束；约束称为等式约束。集合;0)(=x h i X 通常为变量的上下界限定的区域。向量且满足所有约束，则称之为问题的可行解。所有可行解构成可行域。否则,为问题的不可行解,所有不可行解构成不可行域。问题的目标是找到一个可行解X x ∈x 使得)()(x f x f ≤对于所有可行解x 成立。那么，x 为最优解[4]。 2.2算法描述 目前，最常采用的约束处理方法为惩罚函数法。但优化搜索的效率对惩罚因子的选择有
实现遗传算法的0-1背包问题 求解及其改进 姓名： 学号： 班级： 提交日期：2012年6月27日
实现遗传算法的0-1背包问题求解 摘要：研究了遗传算法解决0-1背包问题中的几个问题： 1）对于过程中不满足重量限制条件的个体的处理,通过代换上代最优解保持种群的进化性 2）对于交换率和变异率的理解和处理方法,采用逐个体和逐位判断的处理方法 3）对于早熟性问题,引入相似度衡量值并通过重新生成个体替换最差个体方式保持种群多样性。4）一种最优解只向更好进化方法的尝试。 通过实际计算比较表明,本文改进遗传算法在背包问题求解中具有很好的收敛性、稳定性和计算效率。通过实例计算，表明本文改进遗传算法优于简单遗传算法和普通改进的遗传算法。 关键词：遗传算法；背包问题；优化 1.基本实现原理： 一、问题描述 0-1背包问题属于组合优化问题的一个例子，求解0-1背包问题的过程可以被视作在很多可行解当中求解一个最优解。01背包问题的一般描述如下： 给定n个物品和一个背包，物品i的重量为Wi，其价值为Vi，背包的容量为C。选择合适的物品装入背包，使得背包中装入的物品的总价值最大。注意的一点是，背包内的物品的重量之和不能大于背包的容量C。在选择装入背包的物品时，对每种物品i只有两种选择：装入背包或者不装入背包，即只能将物品i装入背包一次。称此类问题为0/1背包问题。 其数学模型为： 0-1背包问题传统的解决方法有动态规划法、分支界限法、回溯法等等。传统的方法不能有效地解决0-1背包问题。遗传算法（Genetic Algorithms）则是一种适合于在大量的可行解中搜索最优（或次优）解的有效算法。 二、遗传算法特点介绍: 遗传算法(Genetic Algorithm, GA)是1962年Holland教授首次提出了GA算法的思想是近年来随着信息数据量激增，发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。 基本遗传算法求解步骤： Step 1 参数设置：在论域空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率P c 和变异率P m，代数T； Step 2 初始种群：随机产生U中的N个染色体s1, s2, …, s N，组成初始种群S={s1, s2, …, s N}，置代数计数器t=1； Step 3计算适应度：S中每个染色体的适应度f() ； Step 4 判断：若终止条件满足，则取S中适应度最大的染色体作为所求结果，算法结束。Step 5 选择-复制：按选择概率P(x i)所决定的选中机会，每次从S中随机选定1个染色体并将其复制，共做N次，然后将复制所得的N个染色体组成群体S1； Step 6 交叉：按交叉率P c所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； Step 7 变异：按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； Step 8 更新：将群体S3作为新一代种群，即用S3代替S，t=t+1，转步3；
使用遗传算法求解函数最大值 题目 使用遗传算法求解函数 在及y的最大值。 解答 算法 使用遗传算法进行求解，篇末所附源代码中带有算法的详细注释。算法中涉及不同的参数，参数的取值需要根据实际情况进行设定，下面运行时将给出不同参数的结果对比。 定义整体算法的结束条件为，当种群进化次数达到maxGeneration时停止，此时种群中的最优解即作为算法的最终输出。 设种群规模为N，首先是随机产生N个个体，实验中定义了类型Chromosome表示一个个体，并且在默认构造函数中即进行了随机的操作。 然后程序进行若干次的迭代，在每次迭代过程中，进行选择、交叉及变异三个操作。 一选择操作 首先计算当前每个个体的适应度函数值，这里的适应度函数即为所要求的优化函数，然后归一化求得每个个体选中的概率，然后用轮盘赌的方法以允许重复的方式选择选择N个个体，即为选择之后的群体。
但实验时发现结果不好，经过仔细研究之后发现，这里在x、y取某些值的时候，目标函数计算出来的适应值可能会出现负值，这时如果按照把每个个体的适应值除以适应值的总和的进行归一化的话会出现问题，因为个体可能出现负值，总和也可能出现负值，如果归一化的时候除以了一个负值，选择时就会选择一些不良的个体，对实验结果造成影响。对于这个问题，我把适应度函数定为目标函数的函数值加一个正数，保证得到的适应值为正数，然后再进行一般的归一化和选择的操作。实验结果表明，之前的实验结果很不稳定，修正后的结果比较稳定，趋于最大值。 二交叉操作 首先是根据交叉概率probCross选择要交叉的个体进行交叉。
这里根据交叉参数crossnum进行多点交叉，首先随机生成交叉点位置，允许交叉点重合，两个重合的交叉点效果互相抵消，相当于没有交叉点，然后根据交叉点进行交叉操作，得到新的个体。 三变异操作 首先是根据变异概率probMutation选择要变异的个体。 变异时先随机生成变异的位置，然后把改位的01值翻转。
遗传算法求解背包问题 信管专业李鹏 201101002044 一、遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene）编码的一定数目的个体(individual)组成。在每一代，根据问题域中个体的适应度（fitness）大小选择（selection）个体，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），产生出代表新的解集的种群。 二、背包问题描述 背包问题是一个典型的组合优化问题，在计算理论中属于NP完全问题，主要应用于管理中的资源分配，资金预算，投资决策、装载问题的建模。传统“0/1”背包问题可以描述为：把具有一定体积和价值的n件不同种类物品放到一个有限容量的背包里，使得背包中物品的价值总量最大。 三、数学模型 背包问题可以描述如下：假设有n个物体，其重量用表示，价值用表示，背包的最大容量为b。这里和b都大于0。问题是要求背包所装的物体的总价值最大。背包问题的数学模型描述如下： (1) (2) (3) 约束条件(3)中表示物体i被选入背包，反之，表示物体i没有被选入背包。约束条件(2)表示背包的容量约束。
四、使用遗传算法解决“0-1背包问题”的思路：0-1背包的解可以编码为一串0-1字符串（0：不取，1：取）；首先，随机产生M个0-1字符串，然后评价这些0-1字符串作为0-1背包问题的解的优劣；然后，随机选择一些字符串通过交叉、突变等操作产生下一代的M个字符串，而且较优的解被选中的概率要比较高。这样经过G代的进化后就可能会产生出0-1背包问题的一个“近似最优解”。 五、程序整体流程 （1）读取存取包的限种、商品的重要和价值的TXT文件； （2）初始化种群； （3）计算群体上每个个体的适应度值(Fitness) ； （4）评估适应度,对当前群体P(t)中每个个体Pi计算其适应度F(Pi)，适应度表示了该个体的性能好坏； （5）依照Pc选择个体进行交叉操作； （6）仿照Pm对繁殖个体进行变异操作 （7）没有满足某种停止条件，则转第3步，否则进入8 ； （8）输出种群中适应度值最优的个体。 六、代码 function Main() %定义全局变量 global VariableNum POPSIZE MaxGens PXOVER PMutation VariableNum=3 %变量个数 POPSIZE=50 %种群大小 MaxGens=1000 %种群代数 PXOVER=0.8 %交叉概率 PMutation=0.2 %变异概率 %读取数据文件
一种基于遗传算法的K-means聚类算法 一种基于遗传算法的K-means聚类算法 摘要：传统K-means算法对初始聚类中心的选取和样本的输入顺序非常敏感，容易陷入局部最优。针对上述问题，提出了一种基于遗传算法的K-means聚类算法GKA，将K-means算法的局部寻优能力与遗传算法的全局寻优能力相结合，通过多次选择、交叉、变异的遗传操作，最终得到最优的聚类数和初始质心集，克服了传统K-means 算法的局部性和对初始聚类中心的敏感性。关键词：遗传算法；K-means；聚类 聚类分析是一个无监督的学习过程，是指按照事物的某些属性将其聚集成类，使得簇间相似性尽量小，簇内相似性尽量大，实现对数据的分类[1]。聚类分析是数据挖掘 技术的重要组成部分，它既可以作为独立的数据挖掘工具来获取数据库中数据的分布情况，也可以作为其他数据挖掘算法的预处理步骤。聚类分析已成为数据挖掘主要的研究领域，目前已被广泛应用于模式识别、图像处理、数据分析和客户关系管理等领域中。K-means算法是聚类分析中一种基本的划分方法，因其算法简单、理论可靠、收敛速 度快、能有效处理较大数据而被广泛应用，但传统的K-means算法对初始聚类中心敏 感，容易受初始选定的聚类中心的影响而过早地收敛于局部最优解，因此亟需一种能克服上述缺点的全局优化算法。遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化搜索算法。在进化过程中进行的遗传操作包括编码、选择、交叉、变异和适者生存选择。它以适应度函数为依据，通过对种群个体不断进行遗传操作实现种群个体一代代地优化并逐渐逼近最优解。鉴于遗传算法的全局优化性，本文针 对应用最为广泛的K-means方法的缺点，提出了一种基于遗传算法的K-means聚类算法GKA(Genetic K-means Algorithm)，以克服传统K-means算法的局部性和对初始聚类中心的敏感性。用遗传算法求解聚类问题，首先要解决三个问题：(1)如何将聚类问题的解编码到个体中；(2)如何构造适应度函数来度量每个个体对聚 类问题的适应程度，即如果某个个体的编码代表良好的聚类结果，则其适应度就高；反之，其适应度就低。适应度函数类似于有机体进化过程中环境的作用，适应度高的个体 在一代又一代的繁殖过程中产生出较多的后代，而适应度低的个体则逐渐消亡；(3) 如何选择各个遗传操作以及如何确定各控制参数的取值。解决了这些问题就可以利
Using Genetic Algorithms for Dynamic Scheduling
Ana Madureira * Carlos Ramos * Sílvio do Carmo Silva ? anamadur@dei.isep.ipp.pt,, csr@dei.isep.ipp.pt, scarmo@dps.uminho.pt
1
Institute of Engineering Polytechnic of Porto, GECAD - Knowledge Engineering and Decision Support Research Group, Dept. of Computer Science Rua de S?o Tomé, 4200 Porto-Portugal Phone: +351 228340500 Fax: +351 228321159
2 Minho University, Dept. of Production and Systems 4710-057, Braga -– Portugal, Phone: +351 253604745
Abstract
In most practical environments, scheduling is an ongoing reactive process where the presence of real time information continually forces reconsideration and revision of pre-established schedules. Scheduling algorithms that achieve good or near optimal solutions and can efficiently adapt them to perturbations are, in most cases, preferable to those that achieve optimal ones but that cannot implement such an adaptation. This reality, motivated us to concentrate on tools, which could deal with such dynamic, disturbed scheduling problems, both for single and multi-machine manufacturing settings, even though, due to the complexity of these problems, optimal solutions may not be possible to find. We decided to address the problem drawing upon the potential of Genetic Algorithms to deal with such complex situations. We decided to address the problem drawing upon the potential of Genetic Algorithms to deal with such complex situations. Since in a sense natural evolution is a process of continuous adaptation, it seems appropriate to consider Genetic Algorithms as good candidates for dynamic scheduling problems. This paper is concerned with vertical oriented detailed scheduling of Extended Job-Shop on dynamic environments. It addresses the scheduling of tasks, either simple or complex products, comprehending the parts fabrication and their multistage assembly into complex products. Key Words: Dynamic Scheduling, Population Dynamic Adaptation, Regenerating Mechanism, Genetic Algorithms.
1. INTRODUCTION
Research on the theory and practice of scheduling has been pursued for many years. Theoretical scheduling problems concerned with searching for optimal schedules subject to a limited number of constraints have adopted a variety of techniques including branch-and-bound and dynamic programming. From the point of view of combinatorial optimization the question of how to sequence and schedule jobs in a dynamic environment looks rather complex and is known to be NP-hard. For literature on this subject, see for example, Baker (1974), French (1982), Blazewicz et al. (2001), Pinedo (2001) and Brucker (2001). In generic terms, the scheduling process can be defined as the assignment of time-constrained jobs to timeconstrained resources within a pre-defined time framework, which represents the complete time horizon of the schedule. An admissible schedule will have to satisfy a set of hard and soft constraints imposed on jobs and resources. So, a scheduling problems can be seen as a decision making process for operations starting and resources to be used. A variety of characteristics and constraints related with jobs and production system, such as operation processing times, release and due dates, precedence constraints and resource availability, can affect scheduling decisions. If all jobs are known before processing starts a scheduling problem is said to be static, while, to classify a problem as dynamic it is sufficient that job release times are not fixed at a single point in time, i.e. jobs arrive to the system at different times. Scheduling problems can also be classified as either deterministic, when processing times and all other parameters are known and fixed, or as non-deterministic, when some or all parameters are uncertain (French, 1982). Most of the known work on scheduling deals with optimisation of scheduling problems in static environments, whereas, due to several sorts of random occurrences and perturbations, real world scheduling problems are usually of dynamic nature. Due to their dynamic nature, real scheduling problems have additional complexity in relation to static ones. However, in many situations, both static and dynamic problems, even for apparently simple cases, are hard to
背包问题---遗传算法解决 function Population1=GA_copy(Population,p,w0,w) %复制算子 %Population为种群 n=length(Population(:,1)); fvalue=zeros(1,n); for i=1:n fvalue(i)=GA_beibao_fitnessvalue(Population(i,:),p,w0,w); end fval=fvalue/sum(fvalue); F(1)=0; for j=1:n F(j+1)=0; for k=1:j F(j+1)=F(j+1)+fval(k); end end for i=1:n test=rand; for j=1:n if((test>=F(j))&&(test POP(j,z)=Population(i,z); end POP(j,l+1)=i; p(j)=randint(1,1,[1 l-1]); j=j+1; end end k0=j-1; k=floor(k0/2); if k>=1 for m=1:k for t=p(2*m-1)+1:l s=POP(2*m-1,t); POP(2*m-1,t)=POP(2*m,t); POP(2*m,t)=s; end end for m=1:k0 for i=1:l Population1(POP(m,l+1),i)=POP(m,i); end end end function fitnessvalue=GA_fitnessvalue(x,p,w0,w) %使用惩罚法计算适应度值 %x为染色体 %p为背包问题中每个被选物体的价值 %w0为背包问题中背包总容积 %w为背包问题中每个被选物品的容积 l=length(x); for i=1:l a(i)=p(i).*x(i); end f=sum(a); b=min(w0,abs(sum(w)-w0)); for i=1:l wx(i)=w(i).*x(i); end if abs(sum(wx)-w0)>b*0.99 p=0.99; 遗传算法求解VRP 问题的技术报告 摘要：本文通过遗传算法解决基本的无时限车辆调度问题。采用车辆和客户对应排列编码的遗传算法，通过种群初始化，选择，交叉，变异等操作最终得到车辆配送的最短路径。通过MA TLAB 仿真结果可知，通过遗传算法配送的路径为61.5000km,比随机配送路径67km 缩短了5.5km 。此结果表明遗传算法可以有效的求解VRP 问题。 一、 问题描述 1.问题描述 车辆调度问题（Vehicle Scheduling/Routing Problem,VSP/VRP ）的一般定义为[1]：对一系列送货点和/或收货点，组织适当的行车路线，使车辆有序地通过它们，在满足一定的约束条件（如货物需求量、发送量，送发货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用极小、时间尽量少、使用车辆数尽量少等）。问题描述如下[2]：有一个或几个配送中心),...,1(n i D i =，每个配送中心有K 种不同类型的车型，每种车型有n 辆车。有一批配送业务),...,1(n i R i =，已知每个配送业务需求量),...,1(n i q i =和位置或要求在一定的时间范围内完成，求在满足不超过配送车辆载重等的约束条件下，安排配送车辆在合适的时间、最优路线使用成本最小。 2.数学模型 设配送中心有K 台车，每台车的载重量为),...,2,1(K k Q k =，其一次配送的最大行驶距离为k D ，需要向L 个客户送货，每个客户的货物需求量为),...,2,1(L i q i =，客户i 到j 的运距为ij d ，配送中心到各个客户的距离为),...,2,1,(0L j i d j =，再设k n 为第K 台车配送的客户数（k n =0表示未使用第K 台车），用集合k R 表示第k 条路径，其中ki r 表示客户ki r 在路径 k 中的顺序为 （不包括配送中心），令 0k r 表示配送中心，若以配送总里程最短为目标函数，则可建立如下数学模型： ∑∑==?+=-K k k rk r n i r r n sign d d Z k kn k ki i k 101)] ([min )1( (1) k n i ki Q qr k ≤∑=1 (2) k k rk r n i r r D n sign d d k kn k ki i k ≤?+∑=-)(01)1( (3) L n k ≤≤0 (4) 改进的混沌遗传算法 李辉 (计算机学院2004级研究生 04720746) 摘要：混沌遗传算法(chaos genetic algorithm, CGA)是基于混沌优化的遗传操作,将使子代个体均匀地分布于定义空间,从而可避免早熟,以较大的概率实现全局最优搜索.与传统的遗传算法相比较, CGA 的在线和离线性能都有较大的改进。而遗传算法作为一种智能算法，是解决非线性复杂优化问题的有利工具，但它在搜索过程中易陷入局部最优，收敛速度慢的缺陷又限制了它的寻优效能。混沌遗传算法具有两者的优点，大大提高了优化的效率。 关键词：遗传算法混沌混沌优化 Abstract：Chaos genetic algorithm (CGA)is a genetic operation,which based on chaos optimization,makes the individuals of subgeneration distribute uniformly in the defined space and avoids the premature of subgeneration.To compare the performances of the CGA with those of the traditional GA,The results demonstrated that the CGA’s on-line and off–line performance was all superior to that of the traditional GA.As an inteliengence algorithm,GA is a effectual toos to resolve the problem of the liner-optimization,but the slower convergence and the premature restrict its efficiency.And CGA which has the two strongpoint has promoted is efficiency in optimization. Key words: genetic algorithm chaos chaos optimization 1 引言： 遗传算法(GA)最早由美国Michigan大学的John Holland教授提出，通过模拟自然界中的生命进化过程，有指导地而不是盲目地进行随机搜索，适用于在人工系统中解决复杂特定目标的非线性反演问题。De Jong首先将遗传算法应用于函数优化问题的研究，他的工作表明在求解数学规划时，GA是一种有效的方法。但对于大型复杂系统，尤其是非线性系统优化问题的求解，GA仍有许多缺陷，如无法保证收敛到全局最优解，群体中最好的染色体的丢失，进化过程的过早收敛等。 混沌是自然界中一种较为普遍的现象，具有“随机性”、“遍历性”及“规律性”等特点，在一定范围内能按其自身的“规律”不重复地遍历所有状态的。在搜索空间小时混沌优化方法效果显著，但搜索空间大时几乎无能为力。 混沌遗传算法(CGA)的基本思想是将混沌状态引入到优化变量中，并把混沌运动的遍历范围“放大”到优化变量的取值范围，然后把得到的混沌变量进行编码，进行遗传算子操作。再给混沌变量附加—混沌小扰动，通过一代代地不断进化，最后收敛到一个最适合环境的个体上，求得问题的最优解。 2 传统遗传算法 传统遗传算法： population old_pop,new_pop;/*current and next population*/ int pop_size,generation; float p_cross,p_mutation; /*prob. Of crossover & mutation*/ 1 old_pop=initial random population={ind1,ind2,….indpopsize} 2 while(generation 遗传算法求解0-1背包问题 一、问题描述 给定n种物品和容量为C的背包。物品i的重量是wi，其价值为vi。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 二、知识表示 1、状态表示 （1）个体或染色体：问题的一个解，表示为n个比特的字符串，比特值为0表示不选该物品，比特值为1表示选择该物品。 （2）基因：染色体的每一个比特。 （3）种群：解的集合。 （4）适应度：衡量个体优劣的函数值。 2、控制参数 （1）种群规模：解的个数。 （2）最大遗传的代数 （3）交叉率：参加交叉运算的染色体个数占全体染色体的比例，取值范围一般为0.4～0.99。（4）变异率：发生变异的基因位数所占全体染色体的基因总位数的比例，取值范围一般为0.0001～0.1。 3、算法描述 （1）在搜索空间U上定义一个适应度函数f(x)，给定种群规模N，交叉率Pc和变异率Pm，代数T； （2）随机产生U中的N个个体s1, s2, …, sN，组成初始种群S={s1, s2, …, sN}，置代数计数器t=1； （3）计算S中每个个体的适应度f() ； （4）若终止条件满足，则取S中适应度最大的个体作为所求结果，算法结束。 （5）按选择概率P(xi)所决定的选中机会，每次从S中随机选定1个个体并将其染色体复制，共做N次，然后将复制所得的N个染色体组成群体S1； （6）按交叉率Pc所决定的参加交叉的染色体数c，从S1中随机确定c个染色体，配对进行交叉操作，并用产生的新染色体代替原染色体，得群体S2； （7）按变异率P m所决定的变异次数m，从S2中随机确定m个染色体，分别进行变异操作，并用产生的新染色体代替原染色体，得群体S3； （8）将群体S3作为新一代种群，即用S3代替S，t = t+1，转步3。 三、算法实现 1、主要的数据结构 染色体：用一维数组表示，数组中下标为i的元素表示第（i+1）个物品的选中状态，元素值为1，表示物品被选中，元素值为0表示物品不被选中。 种群：用二维数组表示，每一行表示一个染色体。 具有最大价值的染色体：由于每一个染色体经过选择、交叉、变异后都可能发生变化，所以对于产生的新的总群，需要记录每个物品的选中状态。同时保存该状态下物品的最大价值，如果新的总群能够产生更优的值，则替换具有最大价值的染色体。 题目：生成两个整型，求在这两个整形之间cost=x1+x2-10*(cos(2*3.14*x1)+cos(2*3.14*x2))函数的最小值 源程序： #include "stdio.h" #include "stdlib.h" #include "conio.h" #include "math.h" #include "time.h" #define num_C 12 //个体的个数，前6位表示x1，后6位表示x2 #define N 100 //群体规模为100 #define pc 0.9 //交叉概率为0.9 #define pm 0.1 //变异概率为10% #define ps 0.6 //进行选择时保留的比例 #define genmax 2000 //最大代数200 int RandomInteger(int low,int high); void Initial_gen(struct unit group[N]); void Sort(struct unit group[N]); void Copy_unit(struct unit *p1,struct unit *p2); void Cross(struct unit *p3,struct unit *p4); void Varation(struct unit group[N],int i); void Evolution(struct unit group[N]); float Calculate_cost(struct unit *p); void Print_optimum(struct unit group[N],int k); /* 定义个体信息*/ typedef struct unit { int path[num_C]; //每个个体的信息 double cost; //个体代价值 }; struct unit group[N]; //种群变量group int num_gen=0; //记录当前达到第几代 int main() { int i,j; srand((int)time(NULL)); //初始化随机数发生器 Initial_gen(group); //初始化种群 Evolution(group); //进化：选择、交叉、变异 getch(); return 0; } /* 初始化种群*/ void Initial_gen(struct unit group[N]) { 初始遗传算法及一个简单的例子 遗传算法(Genetic Algorithms, GA)是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法。它模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 下面我以一个实例来详细表述遗传算法的过程 例：求下述二元函数的最大值： 2 =] y x x∈ ,0[ 31 1、编码： 用遗传算法求解问题时，不是对所求解问题的实际决策变量直接进行操作，而是对表示可行解的个体编码的操作，不断搜索出适应度较高的个体，并在群体中增加其数量，最终寻找到问题的最优解或近似最优解。因此，必须建立问题的可行解的实际表示和遗传算法的染色体位串结构之间的联系。在遗传算法中，把一个问题的可行解从其解空间转换到遗传算法所能处理的搜索空间的转换方法称之为编码。反之，个体从搜索空间的基因型变换到解空间的表现型的方法称之为解码方法。 编码是应用遗传算法是需要解决的首要问题，也是一个关键步骤。迄今为止人们已经设计出了许多种不同的编码方法。基本遗传算法使用的是二进制符号0和1所组成的二进制符号集｛0，1｝，也就是说，把问题空间的参数表示为基于字符集｛0，1｝构成的染色体位串。每个个体的染色体中所包含的数字的个数L 称为染色体的长度或称为符号串的长度。一般染色体的长度L为一固定的数，如本例的编码为 s1 = 1 0 0 1 0 (17) s2 = 1 1 1 1 0 (30) s3 = 1 0 1 0 1 (21) s4 = 0 0 1 0 0 (4) 表示四个个体，该个体的染色体长度L=5。 2、个体适应度函数 在遗传算法中，根据个体适应度的大小来确定该个体在选择操作中被选定的概率。个体的适应度越大，该个体被遗传到下一代的概率也越大；反之，个体的适应度越小，该个体被遗传到下一代的概率也越小。基本遗传算法使用比例选择操作方法来确定群体中各个个体是否有可能遗传到下一代群体中。为了正确计算不同情况下各个个体的选择概率，要求所有个体的适应度必须为正数或为零，不能是负数。这样，根据不同种类的问题，必须预先确定好由目标函数值到个体适应度之间的转换规则，特别是要预先确定好目标函数值为负数时的处理方法。遗传算法求解VRP问题的技术报告【精品毕业设计】(完整版)
改进的混沌遗传算法
遗传算法求解0-1背包问题(JAVA)
遗传算法求解函数极值
遗传算法求解y=x2 - 副本
相关主题
文本预览