1 Introduction to evolutionary computation

1.1 Introductory remarks

As a recognized field, evolutionary computation is quite young. The term itself was invented as recently as 1991, and it represents an effort to bring together researchers who have been following different approaches to simulating various aspects of evolution. These techniques of genetic algorithms (Chapter 7), evolution strategies (Chapter 8), and evolutionary programming (Chapter 9) have one fundamental commonality: they each involve the reproduction, random variation, competition, and selection of contending individuals in a population. These form the essential essence of evolution, and once these four processes are in place, whether in nature or in a computer, evolution is the inevitable outcome (Atmar 1994). The impetus to simulate evolution on a computer comes from at least four directions.

繁殖室囊、變異膘茎、競(jìng)爭(zhēng)险领、選擇是四大共通點(diǎn)厂僧。

1.2 Optimization

Evolution is an optimization process (Mayr 1988, p 104). Darwin (1859, ch 6) was struck with the ‘organs of extreme perfection’ that have been evolved, one such example being the image-forming eye (Atmar 1976). Optimization does not imply perfection, yet evolution can discover highly precise functional solutions to particular problems posed by an organism’s environment, and even though the mechanisms that are evolved are often overly elaborate from an engineering perspective, function is the sole quality that is exposed to natural selection, and functionality is what is optimized by iterative selection and mutation.

坛怪？？土至？谈飒？？

It is quite natural, therefore, to seek to describe evolution in terms of an algorithm that can be used to solve difficult engineering optimization problems. The classic techniques of gradient descent, deterministic hill climbing, and purely random search (with no heredity) have been generally unsatisfactory when applied to nonlinear optimization problems, especially those with stochastic, temporal, or chaotic components. But these are the problems that nature has seemingly solved so very well. Evolution provides inspiration for computing the solutions to problems that have previously appeared intractable. This was a key foundation for the efforts in evolution strategies (Rechenberg 1965, 1994, Schwefel 1965, 1995).

隨機(jī)和梯度下降在求解非線性問(wèn)題中都不好肪凛，自然看起來(lái)解決的好堰汉。

1.3 Robust adaptation

The real world is never static, and the problems of temporal optimization are some of the most challenging. They require changing behavioral strategies in light of the most recent feedback concerning the success or failure of the current strategy. Holland (1975), under the framework of genetic algorithms (formerly called reproductive plans), described a procedure that can evolve strategies, either in the form of coded strings or as explicit behavioral rule bases called classifier systems (Chapter 12), by exploiting the potential to recombine successful pieces of competing strategies, bootstrapping the knowledge gained by independent individuals. The result is a robust procedure that has the potential to adjust performance based on feedback from the environment.

robust是能根據(jù)反饋調(diào)節(jié)策略的能力辽社。？翘鸭？滴铅？？就乓？

1.4 Machine intelligence

Intelligence may be defined as the capability of a system to adapt its behavior to meet desired goals in a range of environments (Fogel 1995, p xiii). Intelligent behavior then requires prediction, for adaptation to future circumstances requires predicting those circumstances and taking appropriate action. Evolution has created creatures of increasing intelligence over time. Rather than seek to generate machine intelligence by replicating humans, either in the rules they may follow or in their neural connections, an alternative approach to generating machine intelligence is to simulate evolution on a class of predictive algorithms. This was the foundation for the evolutionary programming research of Fogel (1962, Fogel et al 1966).

智力是是一個(gè)系統(tǒng)為適應(yīng)環(huán)境變化做出的適應(yīng)性行為汉匙，需要預(yù)測(cè)采取合適舉措。進(jìn)化創(chuàng)造的個(gè)體智力越來(lái)越高生蚁。噩翠？？邦投？伤锚？

1.5 Biology

Rather than attempt to use evolution as a tool to solve a particular engineering problem, there is a desire to capture the essence of evolution in a computer simulation and use the simulation to gain new insight into the physics of natural evolutionary processes (Ray 1991) (see also Chapter 4). Success raises the possibility of studying alternative biological systems that are merely plausible images of what life might be like in some way. It also raises the question of what properties such imagined systems might have in common with life as evolved on Earth (Langton 1987). Although every model is incomplete, and assessing what life might be like in other instantiations lies in the realm of pure speculation, computer simulations under the rubric of artificial life have generated some patterns that appear to correspond with naturally occurring phenomena.

通過(guò)計(jì)算機(jī)模擬返回去對(duì)自然進(jìn)化加深理解。

1.6 Discussion

The ultimate answer to the question ‘why simulate evolution?’ lies in the lack of good alternatives. We cannot easily germinate another planet, wait several millions of years, and assess how life might develop elsewhere. We cannot easily use classic optimization methods to find global minima in functions when they are surrounded by local minima. We find that expert systems and other attempts to mimic human intelligence are often brittle: they are not robust to changes in the domain of application and are incapable of correctly predicting future circumstances so as to take appropriate action. In contrast, by successfully exploiting the use of randomness, or in other words the useful use of uncertainty, ‘a(chǎn)ll possible pathways are open’ for evolutionary computation (Hofstadter 1995, p 115). Our challenge is, at least in some important respects, to not allow our own biases to constrain the potential for evolutionary computation to discover new solutions to new problems in fascinating and unpredictable ways. However, as always, the ultimate advancement of the field will come from the careful abstraction and interpretation of the natural processes that inspire it.

為什么要演化計(jì)算志衣，因?yàn)闆](méi)有更好的替代品屯援。專家系統(tǒng)？念脯？狞洋？和其他對(duì)人類智力的模擬，不能準(zhǔn)確預(yù)測(cè)以采取措施绿店，不robust吉懊。挑戰(zhàn)是不能因?yàn)槲覀冞x擇的傾向限制了演化計(jì)算解決問(wèn)題的潛力。

2 Possible applications of evolutionary computation

2.1 Introduction

Applications of evolutionary computation (EC) fall into a wide continuum of areas. For convenience, in this chapter they have been split into five broad categories:
? planning
? design
? simulation and identification
? control
? classification.
These categories are by no means meant to be absolute or definitive. They all overlap to some extent, and many applications could rightly appear in more than one of the categories.
A number of bibliographies where more extensive information on EC applications can be found are listed after the references at the end of this chapter.

2.2 Applications in planning

2.2.1 Routing

Perhaps one of the best known combinatorial optimization problems is the traveling salesman problem or TSP (Goldberg and Lingle 1985, Grefenstette 1987, Fogel 1988, Oliver et al 1987, Mu ?hlenbein 1989, Whitley et al 1989, Fogel 1993a, Homaifar et al 1993). A salesman must visit a number of cities, and then return home. In which order should the cities be visited to minimize the distance traveled? Optimizing the tradeoff between speed and accuracy of solution has been one aim (Verhoeven et al 1992).

最知名的問(wèn)題是旅行商問(wèn)題惯吕，旅行商必須訪問(wèn)所有城市然后回家惕它，求最小化總距離的訪問(wèn)順序怕午。在速度和訪問(wèn)路徑不重復(fù)中權(quán)衡废登。

A generalization of the TSP occurs when there is more than one salesman (Fogel 1990). The vehicle routing problem is similar. There is a fleet of vehicles, all based at the same depot. A set of customers must each receive one delivery. Which route should each vehicle take for minimum cost? There are constraints, for example, on vehicle capacity and delivery times (Blanton and Wainwright 1993, Thangia et al 1993).

一個(gè)旅行商問(wèn)題的擴(kuò)展是多個(gè)商人，在一個(gè)車隊(duì)中郁惜。一組顧客每個(gè)人收到一個(gè)貨物堡距，每個(gè)車（商人）應(yīng)該怎么走花費(fèi)最少。

Closely related to this is the transportation problem, in which a single commodity must be distributed to a number of customers from a number of depots. Each customer may receive deliveries from one or more depots. What is the minimum-cost solution? (Michalewicz 1992, 1993).

和這個(gè)問(wèn)題相似的是交通運(yùn)輸問(wèn)題兆蕉，一種貨物必須從很多個(gè)倉(cāng)庫(kù)送到很多顧客手上羽戒。每個(gè)顧客可能從一個(gè)或多個(gè)倉(cāng)庫(kù)收到貨，求最小花費(fèi)的解虎韵。

Planning the path which a robot should take is another route planning problem. The path must be feasible and safe (i.e. it must be achievable within the operational constraints of the robot) and there must be no collisions. Examples include determining the joint motions required to move the gripper of a robot arm between locations (Parker et al 1989, Davidor 1991, McDonnell et al 1992), and autonomous vehicle routing (Jakob et al 1992, Page et al 1992). In unknown areas or nonstatic environments, on-line planning/navigating is required, in which the robot revises its plans as it travels.

測(cè)試機(jī)器人路線是另一個(gè)路線規(guī)劃問(wèn)題易稠。路徑必須可行和安全并且沒(méi)有碰撞。例如決定機(jī)器人到達(dá)目的地關(guān)節(jié)的活動(dòng)包蓝，在未知或者變化的環(huán)境中驶社，需要實(shí)時(shí)規(guī)劃企量。