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.

调度问题是设计在一定时间完成一定活动的方案，活动需要的资源是有限制的，在各种限制中，一个或多个目标被优化。

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完全问题。在一个有很多种机器的制造业工厂，有很多个job要被完成，一个job由很多个task组成。每个task需要特定机器运行特定时间。每个job中的任务必须按指定顺序完成。求最小花费。Husbands边优化边建立调度，因为实际中任务可能改变。

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.

一系列测试设计时间表。

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).

在计算中，调度问题包括在多处理器系统中分配任务给处理器，设计内存缓存替代策略。

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算法用于背包问题，最简单的是一维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用于设计电路系统。

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用于人工神经网络，设计网络拓扑和优化权重集合。

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有很多工程应用，结构设计平面桁架...

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.

模拟包括采用设计或建立模型，然后看系统表现如何。有时不确定什么表现，有时测试准确性。

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是模拟的反过程，包括在以致表现的情况下决定系统的设计。

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.

很多系统可以表示为对一个或多个输入信号产生一个输出信号的模型。提供一系列输入和输出值，系统identification是推断模型具体细节的任务。

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的一个好处是可以推断输入，可以处理噪音等，用于医疗。

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.

空气污染，非传统识别罪犯。

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做一个控制器，用于控制系统。在线使用EA作为控制过程的一部分，因此离线不是关于控制过程的进化，只是关于控制器设计的进化。

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).

燃油机、导航

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).

分类系统。

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).