自适应遗传算法：操作概率动态调整的研究

需积分: 10 81 浏览量更新于2024-08-01 收藏 759KB PDF 举报

身份认证购VIP最低享 7 折!

30元优惠券

"Adapting Operator Probabilities In Genetic Algorithms - Andrew Laurence Tuson MSc Information Technology - University of Edinburgh" 在遗传算法（Genetic Algorithms, GA）中，适应性操作概率是一个重要的研究领域。遗传算法是一种基于自然选择和遗传原理的优化方法，通常用于解决复杂问题的求解。在大多数遗传算法的实现中，操作员（如选择、交叉和变异）的概率通常在算法运行过程中保持固定。然而，有观点认为，这些概率应随算法的进行而动态调整，以适应不断变化的种群特征和优化过程的需求。本论文作者Andrew Laurence Tuson通过实证研究探讨了这一问题。他指出，随着遗传算法的迭代，操作员的能力可能会改变，例如在处理适应度较高的个体时，某些操作可能比其他操作更有效。因此，适应性地调整操作概率可以更好地引导算法向最优解前进。论文对适应性方法在两种不同场景下的效果进行了考察：一是理论上的经典问题，这些问题是遗传算法研究中的基准测试；二是来自运筹学的难题——工作坊调度问题。工作坊调度问题是一个实际应用中的复杂优化问题，涉及多个任务在有限资源下如何高效安排执行顺序。通过实验，作者发现适应性操作概率确实能够影响遗传算法的性能。在某些情况下，动态调整操作概率可以提高算法的收敛速度，找到更优解，而在其他情况下，固定的操作概率可能更为合适。这表明，适应性策略的选择需要根据具体问题的特性进行权衡。此外，作者感谢他的导师Peter Ross博士在整个研究过程中提供的宝贵指导。这项工作不仅为遗传算法的理论研究提供了新的见解，也为实际问题的解决提供了优化策略。适应性操作概率的概念强调了遗传算法灵活性的重要性，为未来的算法设计和改进提供了新的思路。

资源详情

资源推荐

so that applied parameterised uniform crossover is used 70% of the time, with

parameter 0.1 (which means that 90% of the child's genes are from the rst parent

chosen), along with mutation 30% of the time, with a bitwise mutation rate of

0.02. The term `operator settings' will b e taken to mean both of the terms ab ove.

Finally, another term that will be used in this study is `control parameter',

which refers to all of the genetic algorithm design decisions: operator settings,

selection pressure, p opulation size, etc.

Both crossover and mutation will be discussed in more detail below.

Crossover

This is simply an exchange of information b etween two (rarely more) candidate

solutions in the p opulation. This is best illustrated by considering a commonly-

used crossover operator for binary strings.

Two-point crossover picks twopoints, at random, along the strings and swaps

the contents of the string between those points, to pro duce a child as shown in

Figure 1{1.

00000000 00 0

111 1

Crossover

111

000011

1111

Figure 1{1:

Two-Point Crossover

The usual rationale for why crossover can be a useful search operator is that

the recombinative pro cess can bring together portions of separate strings associ-

ated with high tness to produce even tter children (and conversely, bring po or

portions of strings together so they can b e purged from the population).

This is the basis of the

building block hypothesis

Goldberg 89] | a formal

statement of the ability of crossover to combine portions of dierent candidate

solutions (schema or building blocks) associated with high tness to pro duce tter

children.

when it is realised that these vary with the problem being considered, and the

other components of the genetic algorithm.

There is no reason why op erator probabilities must be xed. One argument

against this is that the ability of an op erator to produce new, tter, solutions is not

only dep endent upon the problem b eing attempted, but may also vary depending

upon the current state of the p opulation (for example: if all the solutions in the

population are identical, then crossover is useless).

This idea that an eective assignment of op erator probabilities mayvary with

time, suggests that a time-varying set of probabilities mayimprove solution quality,

or the computational eort required to nd a solution of a given quality, and that

a static set of op erator probabilities is, in eect, a compromise.

Would it be p ossible to develop a schedule in advance which applies the oper-

ators at the appropriate probabilities, at the righttime?

This is seen to b e to be dicult when you takeinto account that the pro cess of

nding appropriate operator probabilities for the basic, static, case is itself quite

hard | varying with the population size, problem, selection metho d, representa-

tion, and the op erators used. In many cases, a through search of the probability

space would be more dicult than the problem that is to b e solved | hence re-

searchers tend to adopt operator probabilities based upon early work by DeJong

DeJong 75] and Grefensette Grefensette 86], however these maywell b e sub opti-

mal for the problem at hand.

Therefore, it maybeadvantageous to employ some form of method that at-

tempts to automatically adjust the op erator probabilities as the genetic algorithm

runs, according to the abilities of the operators present to produce children of im-

proved tness. Work p erformed in this area previously has fallen into two groups:



The direct encoding of op erator probabilities into eachmember of the pop-

ulation, allowing them to `co-evolve' with the solutions.



The use of a global `learning-rule' to adapt op erator probabilities according

to the quality of solutions generated byeac

h op erator.

Unfortunately, no comparisons have been made b etween these approaches.

Also, the

ad hoc

nature of many of these investigations leave doubts as to whether

the work performed is generally applicable, either because of the simple nature of

the problems b eing attempted, or the lack of statistical rigour employed.

However, most work in this area has concentrated on whether these methods

result in adaptation taking place, with the implication that this must be desirable.

The problem with this approach is that it do es not address the `bottom line' - does

applying operator adaptation to the genetic algorithm make it a better optimiser?

The aim of the pro ject is therefore to conduct a systematic investigation into

such metho ds in order to ascertain their utility.

1.4 Outline Of This Dissertation

This chapter has introduced the genetic algorithm paradigm, and highlighted some

of the issues involved in the design of eective algorithms. The diculty of setting

eective op erator probabilities was then expressed. It was argued that possible

gains exist if these probabilities could be adjusted adaptively by the genetic algo-

rithm, to account for the p ossibility that the appropriate operator settings may

be time-varying.

Chapter 2,

A Guide to Operator Adaptation

will rstly review the debate ab out

the relative merits of the two main operators used in GAs, crossover and mutation,

and argue that each are valid search operators in their own right. The dicultyin

setting go od operator probabilities will also be discussed in more detail. This will

set the scene for the main part of this chapter: a literature review on metho ds for

dynamic adaptation of op erator probabilities.

Chapter 3,

The Test Problems

will introduce the reader to part of the metho d-

ology employed in this work: namely the use of a variety of test problems, ranging

from well-studied theoretical problems, to a hard Operations Research/Scheduling

problem. A review of previous work p erformed on these problems will be provided

andanoverview of the GA op erators used for each of the test problems given.

Chapter 4,

A Genetic A

lgorithm For Operator Adaptation

, describes in de-

tail the genetic algorithm used in this investigation, and the op erator adaptation

methods implemented.

剩余148页未读，继续阅读

charry911

粉丝: 0
资源: 2

自适应遗传算法：操作概率动态调整的研究

PEROS Personalized Self-Adapting Operating Systems in the Cloud

Closed-loop Rescheduling using Deep Reinforcement Learning

bending reality: distortion-aware transformers for adapting to panoramic semantic segmentation

pytorch adam

Al is developing rapidly nowadays, what should our country do to keep up with this development?英语写一百字

c++ whether

panda: adapting pretrained features for anomaly detection and segmentation

on content-aware post-processing: adapting statistically learned models

bending reality: distortion-aware transformers for adapting to panoramic sem

spatial position encoding

对人工智能做一次英文的头脑风暴

Domain adaptation

非对称上下文调制算法ACM

用matlab写一个transformer模型

请以“读写能力和科技”为话题作一个英语演讲

SSDA-YOLO的优势

The Key Factors for Success

stm32移植freertos

就各学者关于信号去噪的方法的研究写一篇文献综述，并给出参考资料，格式为“谁干了什么，该方法的优点是什么，缺点是什么”

最新资源