使用Java实现遗传算法解决经典问题

需积分: 9 140 浏览量更新于2024-07-18 收藏 2.09MB PDF 举报

"Genetic Algorithms in Java Basics" 是一本关于使用Java实现遗传算法的专业书籍，由Lee Jacobson和Burak Kanber合著。这本书旨在帮助读者理解和应用遗传算法来解决经典问题，如旅行商问题。遗传算法（Genetic Algorithms，GA）是一种模拟自然选择和遗传学原理的优化方法，属于进化计算的范畴。在Java中实现遗传算法，通常涉及以下几个关键知识点： 1. **基本概念**：遗传算法基于生物进化过程中的遗传、突变和选择等机制。种群是算法的基础，其中包含多个个体（解），每个个体代表可能的解决方案。通过适应度函数评估个体的质量，适应度高的个体更有可能被保留下来。 2. **编码与解码**：在Java中，个体通常用数组、对象或字符串等形式编码，表示问题的潜在解。解码过程则将编码转换为实际的解决方案。 3. **初始化种群**：随机生成初始种群，这是算法的第一步。种群大小、个体的编码方式以及初始解的生成策略都是设计遗传算法时要考虑的因素。 4. **适应度函数**：适应度函数用于衡量个体的优劣，它应反映出目标问题的优化标准。例如，在旅行商问题中，适应度函数可能是总距离。 5. **选择操作**：选择是遗传算法的核心步骤，常用的有轮盘赌选择、锦标赛选择和比例选择等。这些方法根据个体的适应度来决定其在下一代中生存的概率。 6. **交叉操作**（Crossover）：模拟生物的遗传，将两个优秀个体的部分特征组合生成新的个体。常见的交叉策略有单点、多点和均匀交叉等。 7. **变异操作**（Mutation）：为避免算法过早收敛，引入变异操作以保持种群多样性。这通常是随机改变个体的一部分编码。 8. **终止条件**：算法运行直到满足某个停止条件，如达到最大迭代次数、适应度阈值或无明显改进的代数。 9. **实现细节**：在Java中，可以使用面向对象编程来构建遗传算法框架，包括种群类、个体类、操作类（如选择、交叉和变异）等。同时，利用Java的并发特性，可以实现并行化遗传算法以提高效率。 10. **案例分析**：书中通过旅行商问题的实例，详细介绍了如何设计和实现一个完整的遗传算法，帮助读者掌握实际应用技巧。通过阅读此书，读者不仅可以了解遗传算法的基本原理，还能学习如何在Java环境中有效地实现和应用这些算法。无论是对于学术研究还是实际工程问题的求解，这本书都能提供宝贵的指导。

Introduction Chapter 1

their own specific advantages and applications. One successful field, and the one

we’re paying attention to in this book, is evolutionary computation - in which

genetic algorithms make up the majority of the research. Other fields focused on

slightly different areas, such as modeling the human brain. This field of research

is called artificial neural networks, and it uses models of the biological nervous

system to mimic its learning and data processing capabilities.

History of Evolutionary Computation

Evolutionary computation was first explored as an optimization tool in the 1950s

when computer scientists were playing with the idea of applying Darwinian ideas

of biological evolution to a population of candidate solutions. They theorized that

it may be possible to apply evolutionary operators such as crossover – which is an

analog to biological reproduction - and mutation – which is the process in which

new genetic information is added to the genome. It’s these operators when cou-

pled with selection pressure that provide genetic algorithms the ability to “evolve”

new solutions when left over a period of time.

In the 1960s “evolution strategies” – an optimization technique applying

the ideas of natural selection and evolution - was first proposed by Rechenberg

(1965, 1973) and his ideas were later expanded on by Schwefel (1975, 1977). Other

computer scientists at the time were working independently on similar fields of

research such as Fogel L.J; Owens, A.J; and Walsh, M.J (1966), who were the first

to introduce the field of evolutionary programming. Their technique involved

representing candidate solutions as finite-state machines and applying mutation

to create new solutions.

During the 1950s and 1960s some biologists studying evolution began

experimenting with simulating evolution using computers. However, it was

Holland, J.H. (1975) who first invented and developed the concept of genetic

algorithms during the 1960s and 1970s. He finally presented his ideas in 1975 in his

groundbreaking book, “Adaption in Natural and Artificial Systems”. Holland’s book

demonstrated how Darwinian evolution could be abstracted and modeled using

computers for use in optimization strategies. His book explained how biological

chromosomes can be modeled as strings of 1s and 0s, and how populations of

these chromosomes can be “evolved” by implementing techniques that are found

in natural selection such as mutation, selection and crossover.

Holland’s original definition of a genetic algorithm has gradually changed over

the decades from when it was first introduced back in the 1970s. This is somewhat

due to recent researchers working in the field of evolutionary computation

occasionally bringing ideas from the different approaches together. Although this

has blurred the lines between many of the methodologies it has provided us with

rich set of tools which can help us better tackle specific problems. The term “genetic

algorithm” in this book will be used to refer to both Holland’s classical vision of a

genetic algorithm, and also to the wider, present day, interpretation of the words.

Chapter 1 Introduction

Computer scientists to this day are still looking at biology and biological systems

to give them ideas on how they can create better algorithms. One of the more recent

biologically inspired optimization algorithms would be Ant Colony Optimization

which was first proposed in 1992 by Marco, D. (1992). Ant Colony optimization

models the behavior of ants as a method for solving various optimization problems

such as the Traveling Salesman Problem.

The Advantage of Evolutionary Computation

The very rate at which intelligent machines have been adopted within our

society is an acknowledgement of their usefulness. The vast majority of problems

we use computers to solve can be reduced to relatively simple static decision prob-

lems. These problems can become rapidly more complex as the amount of possible

inputs and outputs increase, and only further complicated when the solution needs

to adapt to a changing problem. In addition to this, some problems may also require

an algorithm to search through a huge number of possible solutions in an attempt

to find a feasible solution. Depending on the amount of solutions that need to be

searched through, classical computational methods may not be able find a feasi-

ble solution in the timeframe available – even using a super computer. It’s in these

circumstances where evolutionary computation can offer a helping hand.

To give you an idea of a typical problem we can solve with classical computational

methods, consider a traffic light system. Traffic lights are relatively simple systems

which only require a basic level of intelligence to operate. A traffic light system will

usually have just a few inputs which can alert it to events such as a car or pedestrian

waiting to use the junction. It then needs to manage those inputs and correctly

change the lights in a way in which cars and pedestrians can use the junction

efficiently without causing any accidents. Although, there may be a certain amount

of knowledge required to operate a traffic light system, its inputs and outputs are

basic enough that a set of instructions to operate the traffic light system can be

designed and programmed by humans without much problem.

Often we will need an intelligent system to handle more complex inputs

and outputs. This could mean it is no longer as simple, or maybe impossible, for

a human to program a set of instructions so the machine can correctly map the

inputs to a viable output. In these cases where the complexity of the problem

makes it unpractical for a human programmer to solve with code, optimization and

learning algorithms can provide us with a method to use the computer’s processing

power to find a solution to the problem itself. An example of this might be when

building a fraud detection system that can recognize fraudulent transactions

based on transaction information. Although a relationship may occur between the

transaction data and a fraudulent transaction, it could depend on many subtleties

within the data itself. It’s these subtle patterns in the input that might be hard

for a human to code for, making it a good candidate for applying evolutionary

computation.

Introduction Chapter 1

Evolutionary algorithms are also useful when humans don’t know how to solve

a problem. A classic example of this was when NASA was looking for an antenna

design that met all their requirements for a 2006 space mission. NASA wrote a

genetic algorithm which evolved an antenna design to meetall of their specific

design constraints such as, signal quality, size, weight and cost. In this example

NASA didn’t know how to design an antenna which would fit all their requirements,

so they decided to write a program which could evolve one instead.

Another situation in which we may want to apply an evolutionary computation

strategy is when the problem is constantly changing, requiring an adaptive solution.

This problem can be found when building an algorithm to make predictions on

the stock market. An algorithm that makes accurate predictions about the stock

market one week might not make accurate predictions the following week. This is

due to the forever shifting patterns and trends of the stock market and thus making

prediction algorithms very unreliable unless they’re able to quickly adapt to the

changing patterns as they occur. Evolutionary computation can help accommodate

for these changes by providing a method in which adaptations can be made to the

prediction algorithm as necessary.

Finally, some problems require searching through a large, or possibly, infinite amount

of potential solutions to find the best, or good enough, solution for the problem faced.

Fundamentally, all evolutionary algorithms can be viewed as search algorithms which

search through a set of possible solutions looking the best – or “fittest” - solution. You

may be able to visualize this if you think of all the potential combinations of genes

found in an organism’s genome as candidate solutions. Biological evolution is great

at searching through these possible genetic sequences to find a solution which

sufficiently suits its environment. In larger search spaces it’s likely - even when using

evolutionary algorithms - the best solution to a given problem won’t be found.

However, this is rarely an issue for most optimization problems because typically we

only require a solution good enough to get the job done.

The approach provided by evolutionary computation can be thought of as a

“bottom-up” paradigm. That is when all the complexity that emerges from an

algorithm comes from simple, underlying, rules. The alternative to this would be a

“top-down” approach which would require all the complexity demonstrated within

the algorithm to be written by humans. Genetic algorithms are fairly simple to

develop; making them an appealing choice when otherwise a complex algorithm

is required to solve the problem.

Here is a list of features which can make a problem a good candidate for an

evolutionary algorithm:

• If the problem is sufficiently hard to write code to solve

• When a human isn’t sure how to solve the problem

• If a problem is constantly changing

• When it’s not feasible to search through each possible solution

• When a “good-enough” solution is acceptable

Chapter 1 Introduction

Biological Evolution

Biological evolution, through the process of natural selection, was first proposed

by Charles Darwin (1859) in his book, “The Origin of Species”. It was his concept of

biological evolution which inspired early computer scientists to adapt and use bio-

logical evolution as a model for their optimization techniques, found in evolution-

ary computation algorithms.

Because many of the ideas and concepts used in genetic algorithms stem

directly from biological evolution, a basic familiarity with the subject is useful

for a deeper understanding into the field. With that being said, before we begin

exploring genetic algorithms, let’s first run through the (somewhat simplified)

basics of biological evolution.

All organisms contain DNA which encodes all of the different traits that make

up that organism. DNA can be thought of as life’s instruction manual to create the

organism from scratch. Changing the DNA of an organism will change its traits such

as eye and hair color. DNA is made up of individual genes, and it is these genes that

are responsible for encoding the specific traits of an organism.

An organism’s genes are grouped together in chromosomes and a complete set

of chromosomes make up an organism’s genome. All organisms will have a least

one chromosome, but usually contain many more, for example humans have 46

chromosomes with some species, having more than 1000! In genetic algorithms we

usually refer to the chromosome as the candidate solution. This is because genetic

algorithms typically use a single chromosome to encode the candidate solution.

The various possible settings for a specific trait are called an “allele”, and the

position in the chromosome where that trait is encoded is called a “locus”. We refer

to a specific genome as a “genotype” and the physical organism that genotype

encodes is called the “phenotype”.

When two organisms mate, DNA from both organisms are brought together and

combined in such a way that the resulting organism – usually referred to as the

offspring – acquires 50% of its DNA from its first parent, and the other 50% from

the second. Every so often a gene from the organisms DNA will mutate providing it

with DNA found in neither of its parents. These mutations provide the population

with genetic diversity by adding genes to the population that weren’t available

beforehand. All possible genetic information in the population is referred as the

population’s “gene pool”.

If the resulting organism is fit enough to survive in its environment it’s likely to

mate itself, allowing its DNA to continue on into future populations. If however,

the resulting organism isn’t fit enough to survive and eventually mate its genetic

material won’t propagate into future populations. This is why evolution is

occasionally referred to as survival of the fittest – only the fittest individuals survive

and pass on their DNA. It’s this selective pressure that slowly guides evolution to

find increasingly fitter and better adapted individuals.

剩余161页未读，继续阅读

arjinmc

粉丝: 18
资源: 2

使用Java实现遗传算法解决经典问题

Genetic Algorithm in Java Basics

basic java

Genetic.Algorithms.in.Java.Basics.1484203291

Genetic Algorithms in Java Basics(Apress,2015)

Jenes - Genetic Algorithms for Java-开源

Genetic-Algorithms-in-Java-Basics-master.zip_algorithms_genetic

Genetic Algorithms in Matlab.zip

Genetic algorithms in search, optimization, and machine learning

Genetic Algorithms Library (in Java):适用于需要遗传算法的Java开发人员的API-开源

(GA工具箱索引)Genetic algorithms in control systems engineering.pdf

最新资源