Java语言解析遗传算法实战

需积分: 11 118 浏览量更新于2024-07-18 收藏 2.07MB PDF 举报

"本书《Genetic Algorithms in Java Basics》由Lee Jacobson和Burak Kanber合著，深入浅出地介绍了如何使用Java语言实现遗传算法，并通过解决旅行推销员问题等经典问题来阐述其应用。" 遗传算法是一种模拟自然选择和遗传机制的优化算法，它在解决复杂问题和寻找全局最优解方面具有显著优势。在Java中实现遗传算法，通常包括以下几个关键步骤和概念： 1. 初始化种群：随机生成一组个体（解），这些个体代表可能的解决方案，即初始种群。 2. 适应度函数：定义一个评价个体优劣的标准，即适应度函数。这通常与问题的具体目标相关，如旅行推销员问题中，适应度值可能为总距离的倒数。 3. 选择操作：根据适应度函数的评估结果，选择一部分个体进行繁殖，常见的选择策略有轮盘赌选择、锦标赛选择等。 4. 交叉操作：对选出的两个个体进行基因重组，生成新的后代个体，这是遗传算法的主要创新点，确保了优秀特征的传播。 5. 变异操作：为防止过早收敛，对部分个体进行随机变异，增加种群多样性。 6. 终止条件：设定一定的迭代次数或达到特定的性能指标作为算法停止的条件。在Java中实现遗传算法，可以利用面向对象编程的特点，将个体、种群、选择、交叉和变异等抽象为类，方便代码的组织和复用。同时，Java丰富的库和工具可以帮助我们处理数据结构、计算和图形化展示结果。书中通过解决旅行推销员问题来展示遗传算法的应用。旅行推销员问题是一个经典的组合优化问题，要求找出访问一系列城市并返回起点的最短路径。遗传算法通过搜索庞大的解决方案空间，逐渐逼近最优解。《Genetic Algorithms in Java Basics》这本书为读者提供了理解遗传算法原理和实际编程实现的宝贵资源，适合希望掌握遗传算法并用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页未读，继续阅读

jonasydy

粉丝: 0
资源: 13

Java语言解析遗传算法实战

1204 Java 遗传算法排课java sqlserver.rar_java排课算法_排课_排课系统java_遗传算法Java

GA.rar_GA_GA 遗传算法_java ga_遗传算法 _遗传算法 java

yichuansuanfa.rar_基因_基因遗传算法_遗传算法Java

GA.rar_GA_GA java_java ga_遗传算法 java_閬椾紶绠楁硶 java

TSP.rar_JAVA A星 TSP_Java遗传算法_TSP JAVA_旅行商问题_遗传算法TSP

遗传算法源代码用C语言描述和Java语言描述

遗传算法详细描述.zip

java遗传算法智能组卷

基于遗传算法的JAVA课程排课系统设计源码

遗传算法Java实现与毕业设计应用

最新资源