遗传算法的比较分析与变量交叉和反转概率为操作系统进程调度问题

Er。Rajiv Kumar
博士学位。学者,计算机科学部门& Engg。Singhania UniversityJhunjhunu,拉贾斯坦邦,印度

通讯作者:Er。Rajiv Kumar,电子邮件:rajiv_kumar_gill1@yahoo.co.in

文摘

有许多方法已经开发解决作业车间调度问题和机器流程调度问题。实现操作系统进程调度的遗传算法是一种新的想法。遗传算法是一个健壮的技术解决进程调度和优化问题。有许多类型的遗传算法开发了从简单的遗传算法复杂的并行遗传算法。遗传算法的性能取决于运营商的适当的参数设置用于正在考虑的一个问题。在本文中,我们将分析的性能改良跨越操作系统进程调度问题的遗传算法。调度问题是NP困难问题。改进遗传算法有效地实现操作系统进程调度问题。通过仿真结果,当我们看到交叉和反演算子的概率变化然后遗传算法的收敛性能和状态发生了极大的改变。

关键字

遗传算法、赋权、操作系统、调度、反转。

介绍

进程调度是一个困难的问题在任何操作系统。任何操作系统的性能很大程度上取决于适当的调度的过程。调度问题是认为赋权和所有的算法用于优化这类问题有一个指数的时间;也就是说,计算时间的增加与问题规模成倍增长。多年来,大多数研究人员认为,最优调度是非常困难的任务。与日益增长的兴趣在遗传算法(气)和遗传算法是另一个有前景的全局优化技术[1]用于操作过程调度问题。修改后的交叉遗传算法由戴维斯[2]首次提出,该算法适用于操作系统进程调度问题,拉吉夫等[3]。遗传算法(气)的自适应方法,可用于解决搜索和优化问题。遗传算法(气)首次提出了约翰在1960年代荷兰[4]。这些遗传算法已经应用于许多科学和工程问题[5][6][7]。 The performance of the genetic algorithm is limited by some problem, typically premature convergence. This happens simply because of the accumulation of stochastic errors. If by chance, a gene becomes predominant in the population, then it just as likely to become more predominant in the next generation as it is to become less he predominant. If an increase in predominance is sustained over several successive generations and population is finite, then a gene can be spread to all members of the population. Once gene has converged in this way, it is fixed then crossover cannot introduce new gene values. This produces a ratchet effect, so that as generations go by, each gene eventually becomes fixed. This diverse effect can be minimizing by applying the inversion operator with suitable probability. Here we consider the operating system process scheduling .In this paper we vary the cross over probability with respect to the inversion probability and we will analyze the result.

论文的工作

本文的主要部分,包含在第二节中,将解释工作进程调度遗传算法及其应用的问题。遗传算法是健壮的技术和它没有。的运营商都有自己的属性,遗传算法中的参数设置关注运营商的设置适用于静态值使用。即交叉概率,反转率、人口规模等。可以介绍可以在书中找到戴维斯[8]和戈德堡[9].Section 3描述该遗传算法的结构。第四部分解释了实验装置进行分析和第五节节目考虑问题的实验结果和第六节是结论。

引入遗传算法

概述

评价函数,或目标函数,提供了一个测量的性能对一组特定的参数。衡量性能的适应度函数变换成一个生殖分配的机会。一个字符串代表一组参数的评价是独立于任何其他的评价字符串。健身的字符串,但是,总是定义对当前人口的其他成员。在遗传算法中,健康定义为:fi / fA fi是与字符串相关的评价我和足总平均评价人口中的所有字符串。健身也可以分配基于字符串的人口排名或抽样方法,如比赛选择。遗传算法的执行过程分为两个阶段。它始于当前人口。选择应用于当前的人口创造一个中间人口。然后应用重组和突变中间人口创造下一个人口。 The process of going from the current population to the next population constitutes one generation in the execution of a genetic algorithm. In the first generation the current population is also the initial population. After calculating fi /fA for all the strings in the current population, selection is carried out. The probability that strings in the current population are copied (i.e. duplicated) and placed in the intermediate generation is in proportion to their fitness.

编码

GA可以运行之前,一个合适的编码(或代表)问题必须设计。我们还需要一个适应度函数,将一个灵敏值赋给每个编码的解决方案。在运行期间,父母必须选择底图,重组产生后代。假设一个潜在的解决问题可以表示为一组参数(例如,优化神经网络的参数)。这些参数(称为基因)连接在一起形成一个字符串的值(通常称为染色体。例如,如果我们的问题是最大限度地增加三个变量的函数,F (x);y;z),我们可能代表每个变量由10位二进制数(适当比例)。因此我们的染色体包含三个基因,由30个二进制数字。参数的设置由一个特定的染色体称为基因型。 The genotype contains the information required to construct an organism which is referred to as the phenotype. For example, in a bridge design task, the set of parameters specifying a particular design is the genotype, while the finished construction is the phenotype. The fitness of an individual depends on the performance of the phenotype. This can be inferred from the genotype, i.e. it can be computed from the chromosome, using the fitness function. Assuming the interaction between parameters is nonlinear, the size of the search space is related to the number of bits used in the problem encoding. For a bit string encoding of length L; the size of the search space is 2L and forms a hypercube. The genetic algorithm samples the corners of this L-dimensional hypercube. Generally, most test functions are at least 30 bits in length; anything much smaller represents a space which can be enumerated. Obviously, the expression 2L grows exponentially. As long as the number of "good solutions" to a problem are sparse with respect to the size of the search space, then random search or search by enumeration of a large search space is not a practical form of problem solving. On the other hand, any search other than random search imposes some bias in terms of how it looks for better solutions and where it looks in the search space. A genetic algorithm belongs to the class of methods known as "weak methods" because it makes relatively few assumptions about the problem that is being solved. Genetic algorithms are often described as a global search method that does not use gradient information. Thus, nondifferentiable functions as well as functions with multiple local optima represent classes of problems to which genetic algorithms might be applied. Genetic algorithms, as a weak method, are robust but very general.

适应度函数

必须设计适应度函数为每一个需要解决的问题。给定一个特定的染色体,适应度函数返回一个数值“健身”,或“品质因数”,这应该是成正比的“效用”或“能力”个人、染色体所代表。对于很多问题,尤其是函数优化,适应度函数应该简单地测量值的函数。

选择

确定哪些字符串是“复制”或“选择”交配池和一个字符串多少次将“选择”交配池。表演者将复制经常高于较低的表现。例子:选择一个字符串和一个健身的概率值f f /英国《金融时报》,英国《金融时报》在哪里的健身价值的总和。个人选择使用“随机放回抽样”来填补中间的人口。选择过程将更加接近预期的健康值“余数随机抽样”。For each string i where f/ft is greater than 1.0, the integer portion of this number indicates how many copies of that string are directly placed in the intermediate population. All strings (including those with f/ft less than 1.0) then place additional copies in the intermediate population with a probability corresponding to the fractional portion of f/ft. For example, a string with f/ft = 1:36 places 1 copy in the intermediate population, and then receives a 0:36 chance of placing a second copy. A string with a fitness of f/ft = 0:54 has a 0:54 chance of placing one string in the intermediate population. Remainder stochastic sampling is most efficiently implemented using a method known as stochastic universal sampling. Assume that the population is laid out in random order as in a pie graph, where each individual is assigned space on the pie graph in proportion to fitness. An outer roulette wheel is placed around the pie with N equally spaced pointers. A single spin of the roulette wheel will now simultaneously pick all N members of the intermediate population.

繁殖

后选择进行了中间人口建设完成并可能发生重组。这可以被视为创造未来人口从中间人口。交叉应用于随机配对的字符串表示的一个概率的电脑。(人口应该已经足够慢吞吞地随机选择过程。)选择一双字符串。概率pc“重组”这些字符串形成两个新的字符串插入下一个人口。在该算法我们使用修改后的交叉算子。良好的个人可能会选择在一代几次;贫穷国家可能不是。在选择两个父母,他们的染色体重组,通常使用交叉和变异的机制。 The previous crossover example is known as single point crossover. Crossover is not usually applied to all pairs of individuals selected for mating. A random choice is made, where the likelihood of crossover being applied is typically between 0.6 and 1.0. If crossover is not applied, simply duplicating the parents produces offspring. This gives each individual a chance of passing on its genes without the disruption of crossover. Mutation is applied to each child individually after crossover. It randomly alters each gene with a small probability. The next diagram shows the fifth gene of a chromosome being mutated: The traditional view is that crossover is the more important of the two techniques for rapidly exploring a search space. Mutation provides a small amount of random search, and helps ensure that no point in the search has a zero probability of being examined.

收敛

遗传算法的收敛性与均匀性关注人口的解决方案。当95%的人口拥有相同的结果,那么我们可以说这个基因是收敛的。随着人口的收敛,平均健身方法,最好的人。GA总是服从随机错误。其中一个问题是,遗传漂变。即使没有任何选择的压力(即一个常数适应度函数),成员的人口仍将收敛于解空间的某个时候。这种情况仅仅因为随机误差的累积。偶然,如果一个基因成为占主导地位的人群中,那么它也可能成为下一代更主要是变得不那么主要。如果增加优势持续连续几代,人口是有限的,那么一个基因可以扩散到所有成员的人口。以这种方式一旦o基因聚合,它是固定的; crossover cannot introduce new gene values. This produces a ratchet effect, so that as generations go by, each gene eventually becomes fixed. The rate of genetic drift therefore provides a lower bound on the rate at which a GA can converge towards the correct solution. That is, if the GA is to exploit gradient information in the fitness function, the fitness function must provide a slope sufficiently large to counteract any genetic drift. The rate of genetic drift can be reduced by increasing the mutation rate. However, if the mutation rate is too high, the search becomes effectively random, so once again gradient information in the fitness function is not exploited.

提出了基于遗传算法的结构

交叉遗传算法GA(修改)

(1)开始

(2)初始化种群(随机生成);

(3)健康评估;

(4)重复

(5)选择(Roullete轮选择);

(6)修改交叉;

(7)反演();

(8)健康评估;

”(9)精英主义替代过滤;

(10),直到满足结束条件;

(11)返回找到适当的解决方案;

(12)结束

实验装置

个体是随机生成一个初始种群。一代又一代的繁殖和交叉产生越来越多的个体。

改进的交叉算子和交叉概率电脑是0.6,然后改变反转概率对交叉概率。做成的表现有two-crossover概率(pc) i.e.0.6和1.0交叉算子利用人口或说它可以多样化。但是由于遗传漂变一些时间人口收敛于局部最优点,当时交叉操作不能多样化的人口。反演算子在本质上是探究的,多样化的人口,但总的来说反转的可能性很低。所以在我们的模拟中,我们第一次有0.1反演然后进行概率幅,措施。

仿真结果

在这个实验中我们compare-modified交叉GA two-crossover概率电脑ie 0.6和1.0也有变量反转概率,发现遗传算法的收敛性能和状态大大受到影响。

结论

在本文中,我们审查的影响不同的反转概率对变量交叉概率。结合变化的概率两个运营商将会增强遗传算法的性能。我们发现当反演的概率是非常低的遗传算法过早收敛,也时高则发生同样的情况。所以反转概率不应该非常高或非常低。这是反转概率的情况下。现在的交叉概率,当交叉概率增加然后利用GA的力量增加,没有。迭代的减少。因此遗传算法的性能取决于运营商的GA的适当的参数设置。

引用

大卫E.Goldberg。遗传算法在搜索、优化和机器学习。Addision - Wesley出版公司,有限公司,1989年版。
l戴维斯,“自适应算法应用到Epistactic域”,在进行Int。人工智能(联合Conf. IJCAI”展出85),洛杉矶CA。
R。Kumar博士R .Kumar, S。吉尔,一个。Kaushik”,遗传算法方法操作系统进程调度问题”,国际工程科学与技术杂志》,2010年,页4247 - 4252。
荷兰,J.H.,1975年。“在自然和人工系统适应性”,安阿伯:密歇根大学出版社
M。Srininivas和L.M.Patnaik“遗传算法:一项调查”,IEEE计算机杂志,pp。17-26,1994年6月
L.Davis。作业车间调度的遗传算法。Van Nostrand莱因霍尔德,1990年。
法国,(1982)。排序和调度,介绍数学工作的商店,埃利斯霍尔伍德中校,奇切斯特。