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

需积分: 9 195 浏览量更新于2024-07-15 收藏 1.66MB PDF 举报

"Genetic Algorithms in Java Basics" 是一本关于使用遗传算法解决各种问题的简明教程，书中包含了实际的Java项目和解决方案。作者通过逐步指导，深入浅出地介绍了遗传算法的不同实现及其常见应用，旨在帮助读者掌握如何用遗传算法解决如旅行商问题等经典问题。遗传算法（Genetic Algorithm，简称GA）是一种基于生物进化理论的优化方法，由John Holland在20世纪60年代提出。它模仿自然选择和遗传机制，通过模拟物种的进化过程来寻找问题的最优解。在Java中实现遗传算法，可以构建可扩展、高效的解决方案。本书首先会介绍遗传算法的基本概念，包括种群（Population）、个体（Individual）、基因（Gene）、适应度函数（Fitness Function）以及遗传操作，如选择（Selection）、交叉（Crossover）和变异（Mutation）。适应度函数用于评估个体的优劣，选择过程依据适应度确定哪些个体将进入下一代；交叉和变异则是保证种群多样性和避免早熟的关键步骤。针对旅行商问题，遗传算法通常会将城市视为个体，每个城市之间的距离作为基因，目标是最小化旅行总距离。书中的项目可能涵盖如何定义个体结构、计算适应度、实现选择策略，以及设计合适的交叉和变异操作。在Java编程语言中实现遗传算法，读者将学习到如何使用类和对象来表示种群和个体，如何利用集合框架管理种群，以及如何利用Java的并发特性进行并行计算以加速算法执行。此外，书中可能还会探讨遗传算法与其他优化技术的结合，比如局部搜索，以提升算法性能。这本书是面向进阶读者的，因此，除了基础理论和实现，可能还包括对算法性能分析、参数调优以及如何评估结果等方面的讨论。通过实践项目，读者不仅可以理解遗传算法的工作原理，还能掌握如何在实际问题中应用这些知识。 "Genetic Algorithms in Java Basics" 是一本理想的入门书籍，适合对遗传算法感兴趣，希望通过Java编程实践的开发者。通过学习，读者将能够运用遗传算法解决复杂优化问题，同时提升在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页未读，继续阅读

beapkapchy

粉丝: 0
资源: 5

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

Python遗传算法实战：Leanpub.Genetic.Algorithms.with.Python

机器学习新工具：sklearn-genetic-opt-0.2.1.dev0发布

Java语言解析遗传算法实战

Genetic.Algorithms.in.Java.Basics.1484203291

Genetic Algorithms in Java Basics(Apress,2015)

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

The Role of MATLAB Genetic Algorithms in Complex System Modeling: Strategies and Case Studies

java基因算法源码

From Beginner to Expert】: A Comprehensive Guide to Master Genetic Algorithms for Practical ...

Applications of MATLAB Optimization Algorithms in Machine Learning: Case Studies and Practical Guide

最新资源