2.2.2 Scheduling

Scheduling involves devising a plan to carry out a number of activities over a period of time, where the activities require resources which are limited, there are various constraints and there are one or more objectives to be optimized.

調(diào)度問題是設(shè)計(jì)在一定時(shí)間完成一定活動(dòng)的方案紫谷，活動(dòng)需要的資源是有限制的丛塌，在各種限制中，一個(gè)或多個(gè)目標(biāo)被優(yōu)化帽驯。

Job shop scheduling is a widely studied NP-complete problem (Davis 1985, Biegel and Davern 1990, Syswerda 1991, Yamada and Nakano 1992). The scenario is a manufacturing plant, with machines of different types. There are a number of jobs to be completed, each comprising a set of tasks. Each task requires a particular type of machine for a particular length of time, and the tasks for each job must be completed in a given order. What schedule allows all tasks to be completed with minimum cost? Husbands (1993) has used the additional biological metaphor of an ecosystem. His method optimizes the sequence of tasks in each job at the same time as it builds the schedule. In real job shops the requirements may change while the jobs are being carried out, requiring that the schedule be replanned (Fang et al 1993). In the limit, the manufacturing process runs continuously, so all scheduling must be carried out on-line, as in a chemical flowshop (Cartwright and Tuson 1994).

Job shop問題是被廣泛研究的NP完全問題。在一個(gè)有很多種機(jī)器的制造業(yè)工廠书闸，有很多個(gè)job要被完成尼变，一個(gè)job由很多個(gè)task組成。每個(gè)task需要特定機(jī)器運(yùn)行特定時(shí)間浆劲。每個(gè)job中的任務(wù)必須按指定順序完成嫌术。求最小花費(fèi)。Husbands邊優(yōu)化邊建立調(diào)度牌借，因?yàn)閷?shí)際中任務(wù)可能改變度气。

Another scheduling problem is to devise a timetable for a set of examinations (Corne et al 1994), university lectures (Ling 1992), a staff rota (Easton and Mansour 1993) or suchlike.

一系列測(cè)試設(shè)計(jì)時(shí)間表。

In computing, scheduling problems include efficiently allocating tasks to processors in a multiprocessor system (Van Driessche and Piessens 1992, Kidwell 1993, Fogel and Fogel 1996), and devising memory cache replacement policies (Altman et al 1993).

在計(jì)算中膨报，調(diào)度問題包括在多處理器系統(tǒng)中分配任務(wù)給處理器磷籍，設(shè)計(jì)內(nèi)存緩存替代策略。

2.2.3 Packing

Evolutionary algorithms (EAs) have been applied to many packing problems, the simplest of which is the one-dimensional zero–one knapsack problem. Given a knapsack of a certain capacity, and a set of items, each with a particular size and value, find the set of items with maximum value which can be accommodated in the knapsack. Various real-world problems are of this type: for example, the allocation of communication channels to customers who are charged at different rates.

EA算法用于背包問題现柠，最簡(jiǎn)單的是一維01背包問題院领。

There are various examples of two-dimensional packing problems. When manufacturing items are cut from sheet materials (e.g. metal or cloth), it is desirable to find the most compact arrangement of pieces, so as to minimize the amount of scrap (Smith 1985, Fujita et al 1993). A similar problem arises in the design of layouts for integrated circuits—how should the subcircuits be arranged to minimize the total chip area required (Fourman 1985, Cohoon and Paris 1987, Chan et al 1991)?

二維背包問題，剪裁使碎片最少晒旅，需要的材料面積最小栅盲。

In three dimensions, there are obvious applications in which the best way of packing objects into a restricted space is required. Juliff (1993) has considered the problem of packing goods into a truck for delivery.

三維，在限制空間盛放物品废恋。

2.3 Applications in design

The design of filters has received considerable attention. EAs have been used to design electronic or digital systems which implement a desired frequency response. Both finite impulse response (FIR) and infinite impulse response (IIR) filter structures have been employed (Etter et al 1982, Suckley 1991, Fogel 1991, Fonseca et al 1993, Ifeachor and Harris 1993, Namibar and Mars 1993, Roberts and Wade 1993, Schaffer and Eshelman 1993, White and Flockton 1993, Wicks and Lawson 1993, Wilson and Macleod 1993). EAs have also been used to optimize the design of signal processing systems (San Martin and Knight 1993) and in integrated circuit design (Louis and Rawlins 1991, Rahmani and Ono 1993). The unequal-area facility layout problem (Smith and Tate 1993) is similar to integrated circuit design. It involves finding a two-dimensional arrangement of ‘departments’ such that the distance which information has to travel between departments is minimized.

EA用于設(shè)計(jì)電路系統(tǒng)谈秫。

EC techniques have been widely applied to artificial neural networks, both in the design of network topologies and in the search for optimum sets of weights (Miller et al 1989, Fogel et al 1990, Harp and Samad 1991, Baba 1992, Hancock 1992, Feldman 1993, Gruau 1993, Polani and Uthmann 1993, Romaniuk 1993, Spittle and Horrocks 1993, Zhang and Mu ?hlenbein 1993, Porto et al 1995). They have also been applied to Kohonen feature map design (Polani and Uthmann 1992). Other types of network design problems have also been approached, for example, in telecommunications (Cox et al 1991, Davis and Cox 1993).

EC用于人工神經(jīng)網(wǎng)絡(luò)，設(shè)計(jì)網(wǎng)絡(luò)拓?fù)浜蛢?yōu)化權(quán)重集合鱼鼓。

There have been many engineering applications of EC: structure design, both two-dimensional, such as a plane truss (Lohmann 1992, Watabe and Okino 1993), and three-dimensional, such as aircraft design (Bramlette and Bouchard 1991), actuator placement on space structures (Furuya and Haftka 1993), linear accelerator design, gearbox design, and chemical reactor design (Powell and Skolnick 1993). In relation to high-energy physics, the design of Monte Carlo generators has been tackled.
In order to perform parallel computations requiring global coordination, EC has been used to design cellular automata with appropriate communication mechanisms.
There have also been applications in testing and fault diagnosis. For example, an EA can be used to search for challenging fault scenarios for an autonomous vehicle controller.

EC有很多工程應(yīng)用拟烫，結(jié)構(gòu)設(shè)計(jì)平面桁架...

2.4 Applications in simulation and identification

Simulation involves taking a design or model for a system, and determining how the system will behave. In some cases this is done because we are unsure about the behavior (e.g. when designing a new aircraft). In other cases, the behavior is known, but we wish to test the accuracy of the model.

模擬包括采用設(shè)計(jì)或建立模型，然后看系統(tǒng)表現(xiàn)如何迄本。有時(shí)不確定什么表現(xiàn)硕淑，有時(shí)測(cè)試準(zhǔn)確性。

EC has been applied to difficult problems in chemistry and biology. Roosen and Meyer (1992) used an evolution strategy to determine the equilibrium of chemically reactive systems, by determining the minimum free enthalpy of the compounds involved. The determination of the three-dimensional structure of a protein, given its amino acid sequence, has been tackled (Lucasius et al 1991). Lucasius and Kateman (1992) approached this as a sequenced subset selection problem, using two-dimensional nuclear magnetic resonance spectrum data as a starting point. Others have searched for energetically favorable protein conformations (Schulze-Kremer 1992, Unger and Moult 1993), and used EC to assist with drug design (Gehlhaar et al 1995). EC has been used to simulate how the nervous system learns in order to test an existing theory. Similarly, EC has been used in order to help develop models of biological evolution.
In the field of economics, EC has been used to model economic interaction of competing firms in a market.
Identification is the inverse of simulation. It involves determining the design of a system given its behavior.

Identification是模擬的反過程，包括在以致表現(xiàn)的情況下決定系統(tǒng)的設(shè)計(jì)置媳。

Many systems can be represented by a model which produces a single-valued output in response to one or more input signals. Given a number of observations of input and output values, system identification is the task of deducing the details of the model. Flockton and White (1993) concern themselves with determining the poles and zeros of the system.

很多系統(tǒng)可以表示為對(duì)一個(gè)或多個(gè)輸入信號(hào)產(chǎn)生一個(gè)輸出信號(hào)的模型于樟。提供一系列輸入和輸出值，系統(tǒng)identification是推斷模型具體細(xì)節(jié)的任務(wù)拇囊。

One reason for wanting to identify systems is so that we can predict the output in response to a given set of inputs. EC may also employed to fit equations to noisy, chaotic medical data, in order to predict future values. Janikow and Cai (1992) similarly used EC to estimate statistical functions for survival analysis in clinical trials. In a similar area, Manela et al (1993) used EC to fit spline functions to noisy pharmaceutical fermentation process data.

identification的一個(gè)好處是可以推斷輸入迂曲，可以處理噪音等，用于醫(yī)療寥袭。

EC may also be used to identify the sources of airborne pollution, given data from a number of monitoring points in an urban area—the source apportionment problem. In electromagnetics, Tanaka et al (1993) have applied EC to determining the two-dimensional current distribution in a conductor, given its external magnetic field. Away from conventional system identification, an EC approach has been used to help with identifying criminal suspects. This system helps witnesses to create a likeness of the suspect, without the need to give an explicit description.

空氣污染路捧，非傳統(tǒng)識(shí)別罪犯。

2.5 Applications in control

There are two distinct approaches to the use of EC in control: off-line and on-line. The off-line approach uses an EA to design a controller, which is then used to control the system. The on-line approach uses an EA as an active part of the control process. Therefore, with the off-line approach there is nothing evolutionary about the control process itself, only about the design of the controller.

EC的兩種不同的使用方法传黄。離線和在線杰扫。離線使用EA做一個(gè)控制器，用于控制系統(tǒng)膘掰。在線使用EA作為控制過程的一部分章姓，因此離線不是關(guān)于控制過程的進(jìn)化，只是關(guān)于控制器設(shè)計(jì)的進(jìn)化炭序。

Some researchers (Fogel et al 1966, DeJong 1980) have sought to use the adaptive qualities of EAs in order to build on-line controllers for dynamic systems. The advantage of an evolutionary controller is that it can adapt to cope with systems whose characteristics change over time, whether the change is gradual or sudden. Most researchers, however, have taken the off-line approach to the control of relatively unchanging systems.
Fonseca and Fleming (1993) used an EA to design a controller for a gas turbine engine, to optimize its step response, and a control system has been used to optimize combustion in multiple-burner furnaces and boiler plants. EC has also been applied to the control of guidance and navigation systems (Krishnakumar and Goldberg 1990, 1992).

燃油機(jī)啤覆、導(dǎo)航

Hunt (1992b) has tackled the problem of synthesizing LQG (linear– quadratic–Gaussian) and H∞ (H-infinity) optimal controllers. He has also considered the frequency domain optimization of controllers with fixed structures (Hunt 1992a).
Two control problems which have been well studied are balancing a pole on a movable cart (Fogel 1995), and backing up a trailer truck to a loading bay from an arbitrary starting point (Abu Zitar and Hassoun 1993). In robotics, EAs have been developed which can evolve control systems for visually guided behaviors. They can also learn how to control mobile robots (Kim and Shim 1995), for example, controlling the legs of a six-legged ‘insect’ to make it crawl or walk (Spencer 1993). Alma ?ssy and Verschure (1992) modeled the interaction between natural selection and the adaptation of individuals during their lifetimes to develop an agent with a distributed adaptive control framework which learns to avoid obstacles and locate food sources.

2.6 Applications in classification

As described in Chapter 12, a significant amount of EC research has concerned the theory and practice of classifier systems (CFS) (Booker 1985, Holland 1985, 1987, Holland et al 1987, Robertson 1987, Wilson 1987, Fogarty 1994). Classifier systems are at the heart of many other types of system. For example, many control systems rely on being able to classify the characteristics of their environment before an appropriate control decision can be made. This is true in many robotics applications of EC, for example, learning to control robot arm motion (Patel and Dorigo 1994) and learning to solve mazes (Pipe and Carse 1994).

分類系統(tǒng)。

An important aspect of a classifier system, especially in a control application, is how the state space is partitioned. Many applications take for granted a particular partitioning of the state space, while in others, the appropriate partitioning of the state space is itself part of the problem (Melhuish and Fogarty 1994).