当前位置：文档之家 › A Genetic Algorithm for Designing Parallel Processor Interconnection Networks

A Genetic Algorithm for Designing Parallel Processor Interconnection Networks

  • 格式：pdf
  • 大小：179.16 KB
  • 文档页数：27

A Genetic Algorithm for Designing Parallel ProcessorInterconnection NetworksMorris MardenAbstractParallel processor interconnection networks traditionally have been designed from a known set of topologies based on geometric shapes, called conceptual topologies. However, conceptual topol-ogies only explore a very small portion of the solution space, so they may not produce a very desirable solution. Instead, we propose using a genetic algorithm to design these networks. Our results show that such an algorithm can design lower latency networks than conceptual topolo-gies, using fewer links. In particular, our algorithm, called GAPPIN, can design a network with four links per node that has an average latency that is 24% lower and a maximum latency that is 38% lower than a two-dimensional torus. Furthermore, GAPPIN designed a network using six links per node that has an average latency that is 19% lower and a maximum latency that is 33% lower than a three-dimensional torus. Our algorithm can also model the affects of contention in the network. To ensure that it is practical to implement the networks GAPPIN designs, we modi-fied the algorithm to produce networks in which none of the wires are longer than a maximum length. We show that GAPPIN can create designs for networks in which conceptual topologies fail this constraint. Finally, GAPPIN can also design networks that are optimized for fault toler-ance.Keywords:genetic algorithm, interconnection network, topology, CAD, network modellingAbstractParallel processor interconnection networks traditionally have been designed from a known set of topologies based on geometric shapes, called conceptual topologies. However, conceptual topol-ogies only explore a very small portion of the solution space, so they may not produce a very desirable solution. Instead, we propose using a genetic algorithm to design these networks. Our results show that such an algorithm can design lower latency networks than conceptual topolo-gies, using fewer links. In particular, our algorithm, called GAPPIN, can design a network with four links per node that has an average latency that is 24% lower and a maximum latency that is 38% lower than a two-dimensional torus. Furthermore, GAPPIN designed a network using six links per node that has an average latency that is 19% lower and a maximum latency that is 33% lower than a three-dimensional torus. Our algorithm can also model the affects of contention in the network. To ensure that it is practical to implement the networks GAPPIN designs, we modi-fied the algorithm to produce networks in which none of the wires are longer than a maximum length. We show that GAPPIN can create designs for networks in which conceptual topologies fail this constraint. Finally, GAPPIN can also design networks that are optimized for fault toler-ance.1. IntroductionAs processors continue to become faster and more machines are built using a relatively large number of processors, buses are becoming less able to provide the required bandwidth for such machines. The solution is to use interconnection networks instead of buses. Traditionally, there have been two methods used to design these networks: brute force enumeration and concep-tual topologies. Under brute force enumeration, one tries all possible combinations of connecting the nodes together in the network to find the best solution. This is not feasible to do for a rela-tively large number of processors, as the size of the problem is exponential in terms of the number of nodes in the network and the number of links per node. Therefore, engineers usually use a common set of topologies that are based on geometric shapes to design interconnection networks. We call these topologies “conceptual topologies.” Some examples of conceptual topologies in research and commercial machines are rings (which are used in the SCI protocol [6] and in Data Scalar architectures[4]), trees (used in the Thinking Machines CM-5 [5]), hypercubes (used in the SGI Origin [3]), and multidimensional toruses (used in the Cray T3D and T3E [2]).The problem with these two approaches is that they use two different extremes to search the solution space for designing interconnection networks. The brute force approach looks at the entire solution space, which is simply too large to practically do for reasonably sized systems. Conceptual topologies, on the other hand, only cover a very small portion of the solution space, so one may overlook some more desirable solutions. Therefore, we suggest using an algorithm that intelligently searches a large portion of the solution space without enumerating all possible solu-tions. We do this using a genetic algorithm, which we call the Genetic Algorithm for Parallel Pro-cessing Interconnection Networks (GAPPIN).Genetic algorithms are commonly used to solve a variety of problems. In 1958, Friedberg created the first genetic algorithm, which attempted to make a computer learn by mutating small FORTRAN programs [8, 9]. Today, genetic algorithms are commonly used for VLSI CAD design [10-12]. Genetic algorithms have also been used before in computer architecture. For example,Ring Tree2-D TorusFigure 1: Examples of conceptual topologiesEmer and Gloy studied using genetic algorithms for branch predictors [7]. Genetic algorithms search the solution space by starting with an initial set of solutions, modifying these solutions, and determining if the new solutions are better than the previous generation of solutions. Usually, the solutions are modified by picking two solutions at random (the parent solutions) and combin-ing them in some fashion to create a new solution (the child solution). The algorithm then evalu-ates the costs of the new sets of solutions, which is called the fitness value of the solutions. If the fitness value is worse than a threshold value (often the median or average value), then the solution is discarded. After a certain number of iterations (called generations) have occurred, the algo-rithm reports the best solution.In the past, Lau and Tsang have studied the use of a genetic algorithm to design parallel processor interconnection networks [1]. Their algorithm, however, misses many important issues in optimizing the network. First, their algorithm only minimizes for the maximum latency in the network. In contrast, our algorithm optimizes for average latency in addition to maximum latency. We have also included design constraints in our algorithm. The current version of our algorithm can design networks such that no wires are longer than a maximum length (which will be discussed later in this paper). Second, their algorithm creates a new generation by only per-forming mutations on the current generation. Instead, we believe that one would get much better results by both combining solutions and mutating solutions to create a new generation. Lastly, Lau and Tsang work only compares their algorithm to other genetic algorithms that can be used. We believe that it is important to compare the results of a genetic algorithm to current methods.The first version of our algorithm designed networks that were optimized for performance alone, ignoring constraints of building such a network. Section 2 describes this version of the algorithm and section 3 shows the results of this algorithm. In section 4, we describe a modifica-tion to the algorithm so that it will be able to model the effects of contention on the network. Since many of the networks that the algorithm designed appeared to be difficult to build, we mod-ified the algorithm to prevent any links in the network from being longer than a maximum length. We describe this modification and its results in section 5. Fault tolerance of large networks is becoming an important issue, so in section 6 we discuss modifications to our algorithm to include fault tolerance. Finally, we conclude with some remarks in section 7.2. Algorithm for Designing Networks for Performance2.1 Network ModelGAPPIN models a directly connected network, since it would be much more difficult to create an algorithm to design networks with an arbitrary number of switches. Note that this net-work model is not inherent in the algorithm itself and can be replaced by other models without affecting our algorithm’s basic functionality. All of the links in our network model have the same bandwidth and latency, which is common in interconnetion networks. Messages in the network are all the same length and take a single unit of time to traverse a link in the network. This is the case of packet switched networks, where packets are equal in size and can be considered as mes-sages. The links in the network are bidirectional and can carry a maximum of one message per direction per unit of time. Messages traveling in opposite directions along the same link do not affect one another. A network can implement this using separate wires and queues for each direc-tion of the link. Finally, each node in the system has the same number of links, which is finite in number and specified by the user. This is the case in most networks, since most networks use the same components for each of the nodes in the network (to have a different number of links per node requires one to use different components in the network).We made several simplifications to our network model to avoid many implementation-spe-cific details and to reduce the complexity of the algorithm. First, our model specifies that mes-sages are uniformly distributed across the network (i.e., it is equally likely that a message will be sent between any pairs of nodes in the network). To separate the effects of the topology of the network from the effects of the routing algorithm, we statically route messages in the network using shortest path routing. Since designing the network topology and the routing algorithm are equally difficult problems to solve, we suggest separating these two problems and using a similar algorithm for designing the routing algorithm after designing the network topology. Lastly, we currently do not consider the effects of contention in the network.2.2 Creating the Initial PopulationWhen our algorithm starts, it creates an initial set of solutions for the interconnection net-work. A solution can be viewed as a proposal for the final design of the network and a set of solu-tions is called a population. We create the initial population by first making two lists of nodes: a list of nodes currently connected in the network and a list of nodes not connected in the network. The list of connected nodes initially only holds the first node in the network, which is the seed of the network, and the rest of the nodes are in the list of unconnected nodes. We then randomly connect a node from each list to each other, moving the node from the list of unconnected nodes to the list of connected nodes, until the list of unconnected nodes is empty. This ensures that none of the solutions will be a disconnected network, which is a network in which there is no path to one or more nodes in the network. The remaining links in the network are created by connecting them to random nodes.2.3 Creating New GenerationsIn each iteration, our algorithm creates a new generation of solutions. The new generation of solutions starts out twice as large as the previous generation of solutions. Half of the solutions in the new generation are the previous generation of solutions and the other half are new solutions. This prevents the design of the network from degrading if the new solutions for the network have lower performance than the previous generation of solutions.To create a new solution, our algorithm randomly picks two solutions to mate together to create a new child solution. GAPPIN then creates links for each node in the child solution using two mechanisms: inheritance and mutation. Note that these mechanisms work differently in this algorithm than in a pure genetic algorithm. Inheritance creates a link for a node by randomly picking a parent to inherit from. Next, our algorithm randomly picks a link from the same node in the parent network and copies the link into the child solution. Figure 2 shows an example of cre-ating a new solution using inheritance for the case of 4 nodes with 2 links per node. Figure 2a shows the solutions before any links have been created. In the next step (2b), GAPPIN acquired a link from the first parent and copied this link to the child. For the next link (in part 2c), our algo-rithm chose a link from the second parent and copied the link to the child. At this point, our algo-rithm has finished creating the links for the first node in the child and would continue this process to create links for the rest of the nodes. This example shows that while the child solution has characteristics of both its parents, it is different from both of them.Mutation, which is the second method for creating links in the child solution, creates a link by randomly picking a node to link to. Mutation helps improve the performance of the network by adding variation to the generation of solutions. Without mutation, each generation is limited to being similar to the previous generation of solutions. Our algorithm uses inheritance much more often than mutation, since inheritance has memory (i.e., maintains the good characteristics of pre-vious solutions) and mutation is memory-less (i.e., is not based on characteristics of previous solutions).After creating the new generation, GAPPIN computes the cost of each of the new solu-tions, which is also known as the fitness value. Our algorithm then sorts the solutions of the new generation by their cost. Solutions with a cost less than the median cost survive through the gen-eration and solutions with a cost greater than the median cost are removed from the generation.Cost=αx Average latency +β x Maximum latencyWhereα and β are the weights of the individual components of the cost, which are set by the user.The cost of a network is broken up into two components: average and maximum latencies. We define latency as the number of hops from the source to the destination node. For these laten-cies, the messages will use the shortest path to route from the source to the destination, since we are not modelling contention, so there is no benefit to taking a longer path than necessary. To cal-culate the latencies, we use Dijkstra’s algorithm [20] to find the shortest paths between all pairs of nodes in the network.As mentioned before, our algorithm is not a pure genetic algorithm. If we used a pure genetic algorithm, the algorithm would first convert the configurations of the parent networks to string representations. Next, the algorithm would randomly choose how many links to get from the first parent. Finally, it would get links for the child from the first part of the first parent and the rest of the links would be from the second parent. Instead, we believe that by randomly choosing the links from each parent, the algorithm will search more of the solution space and is less likely to get trapped in a local minima.2.4 User Defined VariablesOur algorithm includes five different variables, which the user can change to affect the manner in which GAPPIN designs networks. These variables are: weights of the terms in the cost function, population size of each generation, number of generations to create, probability to use mutation to create links instead of inheritance, and probability to accept redundant links. First, the weights of the terms in the cost function allow the user to specify the relative importance of the measurements of the cost of a network. For example, in our experiments, we specified the weighting of the terms of the cost function as 1.0 (i.e., average and maximum latencies), which means that each of the terms are equally important. The population size of each generation and the number of generations to create effectively control how long the algorithm will run. The larger these two values are, the larger the portion of the solution space is explored, resulting in a better final design. However, as the value of these variables increase, the time that it takes to cre-ate the final design also increases. The probability to use mutation to create links rather than inheritance allows the user to specify the probability that our algorithm uses mutation instead of inheritance to create a link for the network.Finally, the user can set the probability that the algorithm accepts redundant links when it is designing the network. Redundant links occur when two nodes in the network have more than one direct link to each other. This may be helpful when there is contention in the network, since it can increase the bandwidth between a pair of nodes in the network that have heavy traffic. Forexample, fat trees introduce redundant links to reduce the bottlenecks in tree topologies. How-ever, the more redundant links there are in a network, the more likely the network is a discon-nected network. Disconnected networks are trivially removed from the generation of solutions by the cost function, since they have infinite latencies. Disconnected networks occur more fre-quently with more redundant links, since the redundant links can use up available links that are needed to connect to other nodes. Evaluating disconnected networks wastes time, since they are trivially rejected and the time used to create them could have been used to create valid networks.3. Results3.1 Graphical Representation of ResultsFigure 3 shows the results of our algorithm for designing eight, twelve, and sixteen node systems with three links per node. The twelve and sixteen node systems are typical of the net-works that GAPPIN designs, in that there does not appear to be any particular geometric shape to the topologies. However, in the case of the eight node systems, GAPPIN designs a network with a topology that is similar to a hypercube, but changes two of the links. This network has higher performance than a standard hypercube (8% lower average latency and 33% lower maximum latency), yet is not much more difficult to build than a hypercube. It is interesting that GAPPIN designed a network similar to a conceptual topology for eight nodes, but not for larger systems. The likely reason for this is that with only eight nodes, there are few ways to design the network.(a)(b)(c)Figure 3: Graphical representatioicpp.psn of results with 3 links per node(a) results for 8 nodes, (b) results for 12 nodes, (c) results for 16 nodes.013467910258113.2 Comparison of Results to Conceptual TopologiesName of Topology# of links/node Average Latency Maximum Latency Ring216.0032 Tree (63 nodes)3(but not all used) 6.6810 2-D Torus4 4.008 3-D Torus6 3.006 GAPPIN3 3.947 GAPPIN4 3.035 GAPPIN5 2.674 GAPPIN6 2.434 Table 1: Comparison of latencies for conceptual topologies and results from GAPPIN, forsystems with 64 nodesTo measure how well our algorithm works, we compared the results of the algorithm to conceptual topologies, which are the current accepted method of designing interconnection net-works. Table 1 compares the average and maximum latency results of GAPPIN for a 64 node system to four commonly used conceptual topologies. The latencies in these results are reported from GAPPIN, as described in section 2.3. To create these networks, we specified that the cost function should consider the latencies of the network equally (i.e., the weight of each of the com-ponents was set to 1.0). Note that for the tree, we placed nodes at each of the levels of the tree and not just the leaves, since this matches the network model better and results in lower latencies.As one can see, the resulting designs from the algorithm outperform the conceptual topol-ogy designs. These results demonstrate that the network designed by the algorithm that uses three links per node has higher performance than the two dimensional torus network, which uses four links per node. Likewise, the network that the algorithm designed using four links per node has better performance than the three dimensional torus design, which uses six links per node. Since ports on nodes for links are often expensive, this potentially can yield a large cost savings. Alter-natively, one can use the same number of links one would normally use for a conceptual network and instead have a much higher performance network.3.3 Analysis of GAPPIN Over TimeIn this section, we analyze the behavior of our algorithm over time as it is designing a net-work. This way, we can better understand GAPPIN.Figure 4 shows the average and maximum age of the solutions (i.e., how many generations each solution has survived) over time when our algorithm was designing the network. None of the solutions lasts for a long period of time in our algorithm, which means that GAPPIN continues to improve the design over time. When GAPPIN comes up with a better solution, we believe that it replaces the old solutions with variants of the new one. This accounts for the large spikes in the ages. When our algorithm discovers a new, better solution, the average age drops close to zero, but the maximum age remains well above zero. This means that it takes several generations for the new best solution to affect the entire generation of solutions.4. Contention Modelling4.1 Modifications to the Algorithm to Model ContentionTo model contention, we need to make some changes to the network model. First, we model that the network performs dynamic routing with perfect knowledge of what will be the lowest latency path at the time that the message crosses the network. While real dynamic routing algorithms cannot have perfect knowledge of the best path in the network at any moment in time, they can use global knowledge to guide such routing decisions. For example, Thottethodi et al have proposed a dynamic routing algorithm that collects global information about contention in the network to make decisions about message transmissions [26]. We model moderate contention in the network as each node in turn sending a message to every other node in the system. Mes-sages starting from the same node in the network do not conflict with each other, but messages staring from different nodes do conflict with each other. As mentioned before, messages traveling opposite directions along a link do not conflict with each other, but messages traveling the same direction across a link do conflict with each other. The network then dynamically routes messages around congested links.We define the latencies under moderate contention as the hop count from the source to the destination and does not include the length of time that a message needs to stall in the network. The path that messages take may not be the shortest path, because a longer path may take less time to travel along than the shorter path. Thus, the average and maximum latencies under mod-erate contention give us a measure of the length of alternate paths for messages in the network. If there are no alternate paths between nodes (for example, as in a tree topology), then these laten-cies will be the same as in the cases under no contention.In addition, our algorithm also calculates the standard deviation in the number of mes-sages that are sent along each link in the network under moderate contention. This measurement tells us whether some links in the network are more heavily used than other links in the network, causing these links to become bottlenecks in the network. For example, in a tree topology, there is a large variance in the number of messages along each link of the network, since more messages need to travel through the links near the root of the tree than in the links near the leaves. There-fore, the links at the top of the network are the bottleneck of the tree network. Ideally, all of the links in the network would be equally used, which would correspond to a standard deviation of zero.4.2 Results from Modelling ContentionTable 2 compares the results under moderate contention of the networks designed by the algorithm to the four conceptual topologies for results. Note that for the ring, the contention must have been clustered in one section of the network, causing some messages to take the long route from the source to destination. This is an artifact of our dynamic routing algorithm, which attempts to route around congested links. Not surprisingly, the tree topology has a high variance in the number of messages per link, since the links at the top of tree will be much more heavily used than the links at the bottom of the tree. As with the results under no contention, the network using three links per node designed by our algorithm outperforms the two dimensional torus under contention. Likewise, the network designed by GAPPIN that uses four links per node has higher performance than the three dimensional torus under contention. This shows that our algo-rithm can optimize networks well when including costs with and without contention at the same ofTopology# of links/node Average Latency, some contention Maximum Latency, some contention Standard deviation of # of messages/link Ring218.1661103.19Tree (63 nodes)3(not all used) 6.4810104.922-D Torus4 4.481212.793-D Torus6 3.36108.50GAPPIN3 4.0599.58GAPPIN4 3.238 5.96GAPPIN5 2.937 4.38GAPPIN6 2.646 3.91Table 2: Comparison of costs under moderate contention for conceptual topologies andresults from GAPPIN, for a system with 64 nodes4.3 Analysis of Modelling Contention Over TimeFigure 5 shows the components of the median cost over time of the algorithm for design-ing a system with 128 nodes and 8 links per node, where each of the components of the cost are considered equally. It is important to note that the relationships between the components of the cost are complex. Often, to decrease the overall cost of the network, the costs of one or more components actually increase. For example, early in the algorithm, the change in cost for maxi-mum latency under contention and standard deviation of the number of messages per link are the opposite of one another. Interestingly enough, however, the maximum latency under no conten-tion remains constant over time, unlike the other components of the cost.5. Maximum Wire Length Constraint5.1 Modifications to the Algorithm for the ConstraintAfter looking at the networks designed by GAPPIN, as shown in section 3.1, we had some concerns about how difficult it would be to implement these networks. To solve this problem, we modified our algorithm so that it would design networks in which none of the links are longer than a maximum length. To do this, we first modified the algorithm so that the user would specify the positions of the nodes in the network. These positions may either be the absolute, physical coor-dinates of each of the nodes or relative positions of the nodes (for example, in a backplane system, where the nodes are in a line, node 0 would be at (0, 0), node 1 at (1, 0), node 2 at (2, 0), etc.). The user would also then specify the maximum length that a link in the network could be (in the same units as was used to specify the positions of the nodes). The algorithm estimates the lengths of links by computing the Manhattan distance from the source to the destination node. This type of estimation is often used in the placement stage of VLSI CAD tools for estimating the length of wires [21]. Manhattan distance computes the distance between (x a, y a) and (x b, y b) as:Manhattan Distance = |x a - x b| + |y a - y b|The next change we made to add this constraint was to add link length checking when the algorithm creates new children solutions from parent solutions (see section 2.3). When the algo-rithm attempts to create a link for a node in the child network using either inheritance or mutation, the algorithm must compute the estimated length of the link. If the length of the link is less than the maximum allowed length, the algorithm places the link in the child network. Otherwise, the algorithm attempts to create a new link using inheritance or mutation and keeps creating new links until it either finds a link that has a legal length or the algorithm reaches a threshold. When the algorithm reaches the threshold, it gives up on using inheritance to create the link and switches to solely using mutation. Again, the algorithm rejects links that are too long and keeps trying until it reaches another threshold. If the algorithm reaches the second threshold, it gives up and leaves the link on the node empty. Note that we also added a similar process to the generation of the ini-tial population to ensure that the initial population (see section 2.1) of solutions also meets the length constraint.It is interesting to note that with this simple modification, the algorithm performs a differ-ent type of network design. Without the constraint, the algorithm designs a logical topology for the network, which later must be turned into a physical. This is the same as what happens in con-ceptual topologies, where the topologies themselves do not dictate a particular layout. For exam-ple, there are many different ways in which one can arrange networks based on hypercubes and toruses. However, using the new length constraint, GAPPIN designs both the logical topology and physical layout at the same time, since it now considers the positions of the nodes. This is useful, as it saves designers much of the work of mapping a topology to a physical layout.。

合集下载

人工智能 遗传算法

人工智能 遗传算法

人工智能遗传算法英文回答：Genetic Algorithms for Artificial Intelligence.Genetic algorithms (GAs) are a class of evolutionary algorithms that are inspired by the process of natural selection. They are used to solve optimization problems by iteratively improving a population of candidate solutions.How GAs Work.GAs work by simulating the process of natural selection. In each iteration, the fittest individuals in thepopulation are selected to reproduce. Their offspring are then combined and mutated to create a new population. This process is repeated until a satisfactory solution is found.Components of a GA.A GA consists of the following components:Population: A set of candidate solutions.Fitness function: A function that evaluates thequality of each candidate solution.Selection: The process of choosing the fittest individuals to reproduce.Reproduction: The process of creating new individuals from the selected parents.Mutation: The process of introducing random changes into the new individuals.Applications of GAs.GAs have been used to solve a wide variety of problems, including:Optimization problems.Machine learning.Scheduling.Design.Robotics.Advantages of GAs.GAs offer several advantages over traditional optimization methods, including:They can find near-optimal solutions to complex problems.They are not easily trapped in local optima.They can be used to solve problems with multiple objectives.Disadvantages of GAs.GAs also have some disadvantages, including:They can be computationally expensive.They can be sensitive to the choice of parameters.They can be difficult to terminate.中文回答：人工智能中的遗传算法。

外文文献—遗传算法

外文文献—遗传算法

附录I 英文翻译第一部分英文原文文章来源：书名：《自然赋予灵感的元启发示算法》第二、三章出版社：英国Luniver出版社出版日期：2008Chapter 2Genetic Algorithms2.1 IntroductionThe genetic algorithm (GA), developed by John Holland and his collaborators in the 1960s and 1970s, is a model or abstraction of biolo gical evolution based on Charles Darwin’s theory of natural selection. Holland was the first to use the crossover and recombination, mutation, and selection in the study of adaptive and artificial systems. These genetic operators form the essential part of the genetic algorithm as a problem-solving strategy. Since then, many variants of genetic algorithms have been developed and applied to a wide range of optimization problems, from graph colouring to pattern recognition, from discrete systems (such as the travelling salesman problem) to continuous systems (e.g., the efficient design of airfoil in aerospace engineering), and from financial market to multiobjective engineering optimization.There are many advantages of genetic algorithms over traditional optimization algorithms, and two most noticeable advantages are: the ability of dealing with complex problems and parallelism. Genetic algorithms can deal with various types of optimization whether the objective (fitness) functionis stationary or non-stationary (change with time), linear or nonlinear, continuous or discontinuous, or with random noise. As multiple offsprings in a population act like independent agents, the population (or any subgroup) can explore the search space in many directions simultaneously. This feature makes it ideal to parallelize the algorithms for implementation. Different parameters and even different groups of strings can be manipulated at the same time.However, genetic algorithms also have some disadvantages.The formulation of fitness function, the usage of population size, the choice of the important parameters such as the rate of mutation and crossover, and the selection criteria criterion of new population should be carefully carried out. Any inappropriate choice will make it difficult for the algorithm to converge, or it simply produces meaningless results.2.2 Genetic Algorithms2.2.1 Basic ProcedureThe essence of genetic algorithms involves the encoding of an optimization function as arrays of bits or character strings to represent the chromosomes, the manipulation operations of strings by genetic operators, and the selection according to their fitness in the aim to find a solution to the problem concerned. This is often done by the following procedure:1) encoding of the objectives or optimization functions; 2) defining a fitness function or selection criterion; 3) creating a population of individuals; 4) evolution cycle or iterations by evaluating the fitness of allthe individuals in the population,creating a new population by performing crossover, and mutation,fitness-proportionate reproduction etc, and replacing the old population and iterating again using the new population;5) decoding the results to obtain the solution to the problem. These steps can schematically be represented as the pseudo code of genetic algorithms shown in Fig. 2.1.One iteration of creating a new population is called a generation. The fixed-length character strings are used in most of genetic algorithms during each generation although there is substantial research on the variable-length strings and coding structures.The coding of the objective function is usually in the form of binary arrays or real-valued arrays in the adaptive genetic algorithms. For simplicity, we use binary strings for encoding and decoding. The genetic operators include crossover,mutation, and selection from the population.The crossover of two parent strings is the main operator with a higher probability and is carried out by swapping one segment of one chromosome with the corresponding segment on another chromosome at a random position (see Fig.2.2).The crossover carried out in this way is a single-point crossover. Crossover at multiple points is also used in many genetic algorithms to increase the efficiency of the algorithms.The mutation operation is achieved by flopping the randomly selected bits (see Fig. 2.3), and the mutation probability is usually small. The selection of anindividual in a population is carried out by the evaluation of its fitness, and it can remain in the new generation if a certain threshold of the fitness is reached or the reproduction of a population is fitness-proportionate. That is to say, the individuals with higher fitness are more likely to reproduce.2.2.2 Choice of ParametersAn important issue is the formulation or choice of an appropriate fitness function that determines the selection criterion in a particular problem. For the minimization of a function using genetic algorithms, one simple way of constructing a fitness function is to use the simplest form F = A−y with A being a large constant (though A = 0 will do) and y = f(x), thus the objective is to maximize the fitness function and subsequently minimize the objective function f(x). However, there are many different ways of defining a fitness function.For example, we can use the individual fitness assignment relative to the whole populationwhere is the phenotypic value of individual i, and N is the population size. The appropriateform of the fitness function will make sure that the solutions with higher fitness should be selected efficiently. Poor fitness function may result in incorrect or meaningless solutions.Another important issue is the choice of various parameters.The crossover probability is usually very high, typically in the range of 0.7~1.0. On the other hand, the mutation probability is usually small (usually 0.001 _ 0.05). If is too small, then the crossover occurs sparsely, which is not efficient for evolution. If the mutation probability is too high, the solutions could still ‘jump around’ even if the optimal solution is approaching.The selection criterion is also important. How to select the current population so that the best individuals with higher fitness should be preserved and passed onto the next generation. That is often carried out in association with certain elitism. The basic elitism is to select the most fit individual (in each generation) which will be carried over to the new generation without being modified by genetic operators. This ensures that the best solution is achieved more quickly.Other issues include the multiple sites for mutation and the population size. The mutation at a single site is not very efficient, mutation at multiple sites will increase the evolution efficiency. However, too many mutants will make it difficult for the system to converge or even make the system go astray to the wrong solutions. In reality, if the mutation is too high under high selection pressure, then the whole population might go extinct.In addition, the choice of the right population size is also very important. If the population size is too small, there is not enough evolution going on, and there is a risk for the whole population to go extinct. In the real world, a species with a small population, ecological theory suggests that there is a real danger of extinction for such species. Even the system carries on, there is still a danger of premature convergence. In a small population, if a significantly more fit individual appears too early, it may reproduces enough offsprings so that they overwhelm the whole (small) population. This will eventually drive the system to a local optimum (not the global optimum). On the other hand, if the population is too large, more evaluations of the objectivefunction are needed, which will require extensive computing time.Furthermore, more complex and adaptive genetic algorithms are under active research and the literature is vast about these topics.2.3 ImplementationUsing the basic procedure described in the above section, we can implement the genetic algorithms in any programming language. For simplicity of demonstrating how it works, we have implemented a function optimization using a simple GA in both Matlab and Octave.For the generalized De Jong’s test function where is a positive integer andr > 0 is the half length of the domain. This function has a minimum of at . For the values of , r = 100 and n = 5 as well as a population size of 40 16-bit strings, the variations of the objective function during a typical run are shown in Fig. 2.4. Any two runs will give slightly different results dueto the stochastic nature of genetic algorithms, but better estimates are obtained as the number of generations increases.For the well-known Easom functionit has a global maximum at (see Fig. 2.5). Now we can use the following Matlab/Octave to find its global maximum. In our implementation, we have used fixedlength 16-bit strings. The probabilities of crossover and mutation are respectivelyAs it is a maximization problem, we can use the simplest fitness function F = f(x).The outputs from a typical run are shown in Fig. 2.6 where the top figure shows the variations of the best estimates as they approach while the lower figure shows the variations of the fitness function.% Genetic Algorithm (Simple Demo) Matlab/Octave Program% Written by X S Yang (Cambridge University)% Usage: gasimple or gasimple(‘x*exp(-x)’);function [bestsol, bestfun,count]=gasimple(funstr)global solnew sol pop popnew fitness fitold f range;if nargin<1,% Easom Function with fmax=1 at x=pifunstr=‘-cos(x)*exp(-(x-3.1415926)^2)’;endrange=[-10 10]; % Range/Domain% Converting to an inline functionf=vectorize(inline(funstr));% Generating the initil populationrand(‘state’,0’); % Reset the random generatorpopsize=20; % Population sizeMaxGen=100; % Max number of generationscount=0; % counternsite=2; % number of mutation sitespc=0.95; % Crossover probabilitypm=0.05; % Mutation probabilitynsbit=16; % String length (bits)% Generating initial populationpopnew=init_gen(popsize,nsbit);fitness=zeros(1,popsize); % fitness array% Display the shape of the functionx=range(1):0.1:range(2); plot(x,f(x));% Initialize solution <- initial populationfor i=1:popsize,solnew(i)=bintodec(popnew(i,:));end% Start the evolution loopfor i=1:MaxGen,% Record as the historyfitold=fitness; pop=popnew; sol=solnew;for j=1:popsize,% Crossover pairii=floor(popsize*rand)+1; jj=floor(popsize*rand)+1;% Cross overif pc>rand,[popnew(ii,:),popnew(jj,:)]=...crossover(pop(ii,:),pop(jj,:));% Evaluate the new pairscount=count+2;evolve(ii); evolve(jj);end% Mutation at n sitesif pm>rand,kk=floor(popsize*rand)+1; count=count+1;popnew(kk,:)=mutate(pop(kk,:),nsite);evolve(kk);endend % end for j% Record the current bestbestfun(i)=max(fitness);bestsol(i)=mean(sol(bestfun(i)==fitness));end% Display resultssubplot(2,1,1); plot(bestsol); title(‘Best estimates’); subplot(2,1,2); plot(bestfun); title(‘Fitness’);% ------------- All sub functions ----------% generation of initial populationfunction pop=init_gen(np,nsbit)% String length=nsbit+1 with pop(:,1) for the Signpop=rand(np,nsbit+1)>0.5;% Evolving the new generationfunction evolve(j)global solnew popnew fitness fitold pop sol f;solnew(j)=bintodec(popnew(j,:));fitness(j)=f(solnew(j));if fitness(j)>fitold(j),pop(j,:)=popnew(j,:);sol(j)=solnew(j);end% Convert a binary string into a decimal numberfunction [dec]=bintodec(bin)global range;% Length of the string without signnn=length(bin)-1;num=bin(2:end); % get the binary% Sign=+1 if bin(1)=0; Sign=-1 if bin(1)=1.Sign=1-2*bin(1);dec=0;% floating point.decimal place in the binarydp=floor(log2(max(abs(range))));for i=1:nn,dec=dec+num(i)*2^(dp-i);enddec=dec*Sign;% Crossover operatorfunction [c,d]=crossover(a,b)nn=length(a)-1;% generating random crossover pointcpoint=floor(nn*rand)+1;c=[a(1:cpoint) b(cpoint+1:end)];d=[b(1:cpoint) a(cpoint+1:end)];% Mutatation operatorfunction anew=mutate(a,nsite)nn=length(a); anew=a;for i=1:nsite,j=floor(rand*nn)+1;anew(j)=mod(a(j)+1,2);endThe above Matlab program can easily be extended to higher dimensions. In fact, there is no need to do any programming (if you prefer) because there are many software packages (either freeware or commercial) about genetic algorithms. For example, Matlab itself has an extra optimization toolbox.Biology-inspired algorithms have many advantages over traditional optimization methods such as the steepest descent and hill-climbing and calculus-based techniques due to the parallelism and the ability of locating the very good approximate solutions in extremely very large search spaces.Furthermore, more powerful new generation algorithms can be formulated by combiningexisting and new evolutionary algorithms with classical optimization methods.Chapter 3Ant AlgorithmsFrom the discussion of genetic algorithms, we know that we can improve the search efficiency by using randomness which will also increase the diversity of the solutions so as to avoid being trapped in local optima. The selection of the best individuals is also equivalent to use memory. In fact, there are other forms of selection such as using chemical messenger (pheromone) which is commonly used by ants, honey bees, and many other insects. In this chapter, we will discuss the nature-inspired ant colony optimization (ACO), which is a metaheuristic method.3.1 Behaviour of AntsAnts are social insects in habit and they live together in organized colonies whose population size can range from about 2 to 25 millions. When foraging, a swarm of ants or mobile agents interact or communicate in their local environment. Each ant can lay scent chemicals or pheromone so as to communicate with others, and each ant is also able to follow the route marked with pheromone laid by other ants. When ants find a food source, they will mark it with pheromone and also mark the trails to and from it. From the initial random foraging route, the pheromone concentration varies and the ants follow the route with higher pheromone concentration, and the pheromone is enhanced by the increasing number of ants. As more and more ants follow the same route, it becomes the favoured path. Thus, some favourite routes (often the shortest or more efficient) emerge. This is actually a positive feedback mechanism.Emerging behaviour exists in an ant colony and such emergence arises from simple interactions among individual ants. Individual ants act according to simple and local information (such as pheromone concentration) to carry out their activities. Although there is no master ant overseeing the entire colony and broadcasting instructions to the individual ants, organized behaviour still emerges automatically. Therefore, such emergent behaviour is similar to other self-organized phenomena which occur in many processes in nature such as the pattern formation in animal skins (tiger and zebra skins).The foraging pattern of some ant species (such as the army ants) can show extraordinary regularity. Army ants search for food along some regular routes with an angle of about apart. We do not know how they manage to follow such regularity, but studies show that they could move in an area and build a bivouac and start foraging. On the first day, they forage in a random direction, say, the north and travel a few hundred meters, then branch to cover a large area. The next day, they will choose a different direction, which is about from the direction on the previous day and cover a large area. On the following day, they again choose a different direction about from the second day’s direction. In this way, they cover the whole area over about 2 weeks and they move out to a different location to build a bivouac and forage again.The interesting thing is that they do not use the angle of (this would mean that on the fourth day, they will search on the empty area already foraged on the first day). The beauty of this angle is that it leaves an angle of about from the direction on the first day. This means they cover the whole circle in 14 days without repeating (or covering a previously-foraged area). This is an amazing phenomenon.3.2 Ant Colony OptimizationBased on these characteristics of ant behaviour, scientists have developed a number ofpowerful ant colony algorithms with important progress made in recent years. Marco Dorigo pioneered the research in this area in 1992. In fact, we only use some of the nature or the behaviour of ants and add some new characteristics, we can devise a class of new algorithms.The basic steps of the ant colony optimization (ACO) can be summarized as the pseudo code shown in Fig. 3.1.Two important issues here are: the probability of choosing a route, and the evaporation rate of pheromone. There are a few ways of solving these problems although it is still an area of active research. Here we introduce the current best method. For a network routing problem, the probability of ants at a particular node to choose the route from node to node is given bywhere and are the influence parameters, and their typical values are .is the pheromone concentration on the route between and , and the desirability ofthe same route. Some knowledge about the route such as the distance is often used so that ,which implies that shorter routes will be selected due to their shorter travelling time, and thus the pheromone concentrations on these routes are higher.This probability formula reflects the fact that ants would normally follow the paths with higher pheromone concentrations. In the simpler case when , the probability of choosing a path by ants is proportional to the pheromone concentration on the path. The denominator normalizes the probability so that it is in the range between 0 and 1.The pheromone concentration can change with time due to the evaporation of pheromone. Furthermore, the advantage of pheromone evaporation is that the system could avoid being trapped in local optima. If there is no evaporation, then the path randomly chosen by the first ants will become the preferred path as the attraction of other ants by their pheromone. For a constant rate of pheromone decay or evaporation, the pheromone concentration usually varies with time exponentiallywhere is the initial concentration of pheromone and t is time. If , then we have . For the unitary time increment , the evaporation can beapproximated by . Therefore, we have the simplified pheromone update formula:where is the rate of pheromone evaporation. The increment is the amount of pheromone deposited at time t along route to when an ant travels a distance . Usually . If there are no ants on a route, then the pheromone deposit is zero.There are other variations to these basic procedures. A possible acceleration scheme is to use some bounds of the pheromone concentration and only the ants with the current global best solution(s) are allowed to deposit pheromone. In addition, certain ranking of solution fitness can also be used. These are hot topics of current research.3.3 Double Bridge ProblemA standard test problem for ant colony optimization is the simplest double bridge problem with two branches (see Fig. 3.2) where route (2) is shorter than route (1). The angles of these two routes are equal at both point A and pointB so that the ants have equal chance (or 50-50 probability) of choosing each route randomly at the initial stage at point A.Initially, fifty percent of the ants would go along the longer route (1) and the pheromone evaporates at a constant rate, but the pheromone concentration will become smaller as route (1) is longer and thus takes more time to travel through. Conversely, the pheromone concentration on the shorter route will increase steadily. After some iterations, almost all the ants will move along the shorter route. Figure 3.3 shows the initial snapshot of 10 ants (5 on each route initially) and the snapshot after 5 iterations (or equivalent to 50 ants have moved along this section). Well, there are 11 ants, and one has not decided which route to follow as it just comes near to the entrance.Almost all the ants (well, about 90% in this case) move along the shorter route.Here we only use two routes at the node, it is straightforward to extend it to the multiple routes at a node. It is expected that only the shortest route will be chosen ultimately. As any complex network system is always made of individual nodes, this algorithms can be extended to solve complex routing problems reasonably efficiently. In fact, the ant colony algorithms have been successfully applied to the Internet routing problem, the travelling salesman problem, combinatorial optimization problems, and other NP-hard problems.3.4 Virtual Ant AlgorithmAs we know that ant colony optimization has successfully solved NP-hard problems such asthe travelling salesman problem, it can also be extended to solve the standard optimization problems of multimodal functions. The only problem now is to figure out how the ants will move on an n-dimensional hyper-surface. For simplicity, we will discuss the 2-D case which can easily be extended to higher dimensions. On a 2D landscape, ants can move in any direction or , but this will cause some problems. How to update the pheromone at a particular point as there are infinite number of points. One solution is to track the history of each ant moves and record the locations consecutively, and the other approach is to use a moving neighbourhood or window. The ants ‘smell’ the pheromone concentration of their neighbourhood at any particular location.In addition, we can limit the number of directions the ants can move by quantizing the directions. For example, ants are only allowed to move left and right, and up and down (only 4 directions). We will use this quantized approach here, which will make the implementation much simpler. Furthermore, the objective function or landscape can be encoded into virtual food so that ants will move to the best locations where the best food sources are. This will make the search process even more simpler. This simplified algorithm is called Virtual Ant Algorithm (VAA) developed by Xin-She Yang and his colleagues in 2006, which has been successfully applied to topological optimization problems in engineering.The following Keane function with multiple peaks is a standard test functionThis function without any constraint is symmetric and has two highest peaks at (0, 1.39325) and (1.39325, 0). To make the problem harder, it is usually optimized under two constraints:This makes the optimization difficult because it is now nearly symmetric about x = y and the peaks occur in pairs where one is higher than the other. In addition, the true maximum is, which is defined by a constraint boundary.Figure 3.4 shows the surface variations of the multi-peaked function. If we use 50 roaming ants and let them move around for 25 iterations, then the pheromone concentrations (also equivalent to the paths of ants) are displayed in Fig. 3.4. We can see that the highest pheromoneconcentration within the constraint boundary corresponds to the optimal solution.It is worth pointing out that ant colony algorithms are the right tool for combinatorial and discrete optimization. They have the advantages over other stochastic algorithms such as genetic algorithms and simulated annealing in dealing with dynamical network routing problems.For continuous decision variables, its performance is still under active research. For the present example, it took about 1500 evaluations of the objective function so as to find the global optima. This is not as efficient as other metaheuristic methods, especially comparing with particle swarm optimization. This is partly because the handling of the pheromone takes time. Is it possible to eliminate the pheromone and just use the roaming ants? The answer is yes. Particle swarm optimization is just the right kind of algorithm for such further modifications which will be discussed later in detail.第二部分中文翻译第二章遗传算法2.1 引言遗传算法是由John Holland和他的同事于二十世纪六七十年代提出的基于查尔斯·达尔文的自然选择学说而发展的一种生物进化的抽象模型。

遗传算法（英文原文）

遗传算法（英文原文）

What is a genetic algorithm?●Methods of representation●Methods of selection●Methods of change●Other problem-solving techniquesConcisely stated, a genetic algorithm (or GA for short) is a programming technique that mimics biological evolution as a problem-solving strategy. Given a specific problem to solve, the input to the GA is a set of potential solutions to that problem, encoded in some fashion, and a metric called a fitness function that allows each candidate to be quantitatively evaluated. These candidates may be solutions already known to work, with the aim of the GA being to improve them, but more often they are generated at random.The GA then evaluates each candidate according to the fitness function. In a pool of randomly generated candidates, of course, most will not work at all, and these will be deleted. However, purely by chance, a few may hold promise - they may show activity, even if only weak and imperfect activity, toward solving the problem.These promising candidates are kept and allowed to reproduce. Multiple copies are made of them, but the copies are not perfect; random changes are introduced during the copying process. These digital offspring then go on to the next generation, forming a new pool of candidate solutions, and are subjected to a second round of fitness evaluation. Those candidate solutions which were worsened, or made no better, by the changes to their code are again deleted; but again, purely by chance, the random variations introduced into the population may have improved some individuals, making them into better, more complete or more efficient solutions to the problem at hand. Again these winning individuals are selected and copied over into the next generation with random changes, and the process repeats. The expectation is that the average fitness of the population will increase each round, and so by repeating this process for hundreds or thousands of rounds, very good solutions to the problem can be discovered.As astonishing and counterintuitive as it may seem to some, genetic algorithms have proven to be an enormously powerful and successful problem-solving strategy, dramatically demonstratingthe power of evolutionary principles. Genetic algorithms have been used in a wide variety of fields to evolve solutions to problems as difficult as or more difficult than those faced by human designers. Moreover, the solutions they come up with are often more efficient, more elegant, or more complex than anything comparable a human engineer would produce. In some cases, genetic algorithms have come up with solutions that baffle the programmers who wrote the algorithms in the first place!Methods of representationBefore a genetic algorithm can be put to work on any problem, a method is needed to encode potential solutions to that problem in a form that a computer can process. One common approach is to encode solutions as binary strings: sequences of 1's and 0's, where the digit at each position represents the value of some aspect of the solution. Another, similar approach is to encode solutions as arrays of integers or decimal numbers, with each position again representing some particular aspect of the solution. This approach allows for greater precision and complexity than the comparatively restricted method of using binary numbers only and often "is intuitively closer to the problem space" (Fleming and Purshouse 2002, p. 1228).This technique was used, for example, in the work of Steffen Schulze-Kremer, who wrote a genetic algorithm to predict the three-dimensional structure of a protein based on the sequence of amino acids that go into it (Mitchell 1996, p. 62). Schulze-Kremer's GA used real-valued numbers to represent the so-called "torsion angles" between the peptide bonds that connect amino acids. (A protein is made up of a sequence of basic building blocks called amino acids, which are joined together like the links in a chain. Once all the amino acids are linked, the protein folds up into a complex three-dimensional shape based on which amino acids attract each other and which ones repel each other. The shape of a protein determines its function.) Genetic algorithms for training neural networks often use this method of encoding also.A third approach is to represent individuals in a GA as strings of letters, where each letter again stands for a specific aspect of the solution. One example of this technique is Hiroaki Kitano's "grammatical encoding" approach, where a GA was put to the task of evolving a simple set of rules called a context-freegrammar that was in turn used to generate neural networks for a variety of problems (Mitchell 1996, p. 74).The virtue of all three of these methods is that they make it easy to define operators that cause the random changes in the selected candidates: flip a 0 to a 1 or vice versa, add or subtract from the value of a number by a randomly chosen amount, or change one letter to another. (See the section on Methods of change for more detail about the genetic operators.) Another strategy, developed principally by John Koza of Stanford University and called genetic programming, represents programs as branching data structures called trees (Koza et al. 2003, p. 35). In this approach, random changes can be brought about by changing the operator or altering the value at a given node in the tree, or replacing one subtree with another.Figure 1:Three simple program trees of the kind normally used in genetic programming. The mathematical expression that each one represents is given underneath.It is important to note that evolutionary algorithms do not need to represent candidate solutions as data strings of fixed length. Some do represent them in this way, but others do not; for example, Kitano's grammatical encoding discussed above can be efficiently scaled to create large and complex neural networks, and Koza's genetic programming trees can grow arbitrarily large as necessary to solve whatever problem they are applied to.Methods of selectionThere are many different techniques which a genetic algorithm can use to select the individuals to be copied over into the next generation, but listed below are some of the most common methods.Some of these methods are mutually exclusive, but others can be and often are used in combination.Elitist selection: The most fit members of each generation are guaranteed to be selected. (Most GAs do not use pure elitism, but instead use a modified form where the single best, or a few of the best, individuals from each generation are copied into the next generation just in case nothing better turns up.)Fitness-proportionate selection: More fit individuals are more likely, but not certain, to be selected.Roulette-wheel selection: A form of fitness-proportionate selection in which the chance of an individual's being selected is proportional to the amount by which its fitness is greater or less than its competitors' fitness. (Conceptually, this can be represented as a game of roulette - each individual gets a slice of the wheel, but more fit ones get larger slices than less fit ones. The wheel is then spun, and whichever individual "owns" the section on which it lands each time is chosen.)Scaling selection: As the average fitness of the population increases, the strength of the selective pressure also increases and the fitness function becomes more discriminating. This method can be helpful in making the best selection later on when all individuals have relatively high fitness and only small differences in fitness distinguish one from another.Tournament selection: Subgroups of individuals are chosen from the larger population, and members of each subgroup compete against each other. Only one individual from each subgroup is chosen to reproduce.Rank selection: Each individual in the population is assigned a numerical rank based on fitness, and selection is based on this ranking rather than absolute differences in fitness. The advantage of this method is that it can prevent very fit individuals from gaining dominance early at the expense of less fit ones, which would reduce the population's genetic diversity and might hinder attempts to find an acceptable solution.Generational selection: The offspring of the individuals selected from each generation become the entire next generation. No individuals are retained between generations.Steady-state selection: The offspring of the individuals selected from each generation go back into the pre-existing gene pool, replacing some of the less fit members of the previous generation. Some individuals are retained between generations.Hierarchical selection: Individuals go through multiple rounds of selection each generation. Lower-level evaluations are faster and less discriminating, while those that survive to higher levels are evaluated more rigorously. The advantage of this method is that it reduces overall computation time by using faster, less selective evaluation to weed out the majority of individuals that show little or no promise, and only subjecting those who survive this initial test to more rigorous and more computationally expensive fitness evaluation.Methods of changeOnce selection has chosen fit individuals, they must be randomly altered in hopes of improving their fitness for the next generation. There are two basic strategies to accomplish this. The first and simplest is called mutation. Just as mutation in living things changes one gene to another, so mutation in a genetic algorithm causes small alterations at single points in an individual's code.The second method is called crossover, and entails choosing two individuals to swap segments of their code, producing artificial "offspring" that are combinations of their parents. This process is intended to simulate the analogous process of recombination that occurs to chromosomes during sexual reproduction. Common forms of crossover include single-point crossover, in which a point of exchange is set at a random location in the two individuals' genomes, and one individual contributes all its code from before that point and the other contributes all its code from after that point to produce an offspring, and uniform crossover, in which the value at any given location in the offspring's genome is either the value of one parent's genome at that location or the value of the other parent's genome at that location, chosen with 50/50 probability.Figure 2:Crossover and mutation. The above diagrams illustrate the effect of each of these genetic operators on individuals in a population of 8-bit strings. The upper diagram shows two individuals undergoing single-point crossover; the point of exchange is set between the fifth and sixth positions in the genome, producing a new individual that is a hybrid of its progenitors. The second diagram shows an individual undergoing mutation at position 4, changing the 0 at that position in its genome to a 1.Other problem-solving techniquesWith the rise of artificial life computing and the development of heuristic methods, other computerizedproblem-solving techniques have emerged that are in some ways similar to genetic algorithms. This section explains some of these techniques, in what ways they resemble GAs and in what ways they differ.Neural networksA neural network, or neural net for short, is a problem-solving method basedon a computer model of how neurons are connected in the brain. A neuralnetwork consists of layers of processing units called nodes joined bydirectional links: one input layer, one output layer, and zero or more hiddenlayers in between. An initial pattern of input is presented to the input layer ofthe neural network, and nodes that are stimulated then transmit a signal to thenodes of the next layer to which they are connected. If the sum of all theinputs entering one of these virtual neurons is higher than that neuron'sso-called activation threshold, that neuron itself activates, and passes on itsown signal to neurons in the next layer. The pattern of activation thereforespreads forward until it reaches the output layer and is there returned as asolution to the presented input. Just as in the nervous system of biologicalorganisms, neural networks learn and fine-tune their performance over timevia repeated rounds of adjusting their thresholds until the actual outputmatches the desired output for any given input. This process can be supervisedby a human experimenter or may run automatically using a learning algorithm(Mitchell 1996, p. 52). Genetic algorithms have been used both to build and totrain neural networks.Figure 3:A simple feedforward neural network, with one input layer consisting of four neurons, one hidden layer consisting of three neurons, and one output layer consisting of four neurons. The number on each neuron represents its activation threshold: it will only fire if it receives at least that many inputs. The diagram shows the neural network being presented with an input string and shows how activation spreads forward through thenetwork to produce an output.Hill-climbingSimilar to genetic algorithms, though more systematic and less random, ahill-climbing algorithm begins with one initial solution to the problem at hand, usually chosen at random. The string is then mutated, and if the mutationresults in higher fitness for the new solution than for the previous one, thenew solution is kept; otherwise, the current solution is retained. The algorithmis then repeated until no mutation can be found that causes an increase in thecurrent solution's fitness, and this solution is returned as the result (Koza et al.2003, p. 59). (To understand where the name of this technique comes from,imagine that the space of all possible solutions to a given problem isrepresented as a three-dimensional contour landscape. A given set ofcoordinates on that landscape represents one particular solution. Thosesolutions that are better are higher in altitude, forming hills and peaks; thosethat are worse are lower in altitude, forming valleys. A "hill-climber" is thenan algorithm that starts out at a given point on the landscape and movesinexorably uphill.) Hill-climbing is what is known as a greedy algorithm,meaning it always makes the best choice available at each step in the hopethat the overall best result can be achieved this way. By contrast, methodssuch as genetic algorithms and simulated annealing, discussed below, are notgreedy; these methods sometimes make suboptimal choices in the hopes thatthey will lead to better solutions later on.Simulated annealingAnother optimization technique similar to evolutionary algorithms is known as simulated annealing. The idea borrows its name from the industrial process of annealing in which a material is heated to above a critical point to soften it, then gradually cooled in order to erase defects in its crystalline structure, producing a more stable and regular lattice arrangement of atoms (Haupt and Haupt 1998, p. 16). In simulated annealing, as in genetic algorithms, there is a fitness function that defines a fitness landscape; however, rather than a population of candidates as in GAs, there is only one candidate solution.Simulated annealing also adds the concept of "temperature", a global numerical quantity which gradually decreases over time. At each step of the algorithm, the solution mutates (which is equivalent to moving to an adjacent point of the fitness landscape). The fitness of the new solution is then compared to the fitness of the previous solution; if it is higher, the new solution is kept. Otherwise, the algorithm makes a decision whether to keep or discard it based on temperature. If the temperature is high, as it is initially, even changes that cause significant decreases in fitness may be kept and used as the basis for the next round of the algorithm, but as temperature decreases, the algorithm becomes more and more inclined to only accept fitness-increasing changes. Finally, the temperature reaches zero and the system "freezes"; whatever configuration it is in at that point becomes the solution. Simulated annealing is often used for engineering design applications such as determining the physical layout of components on a computer chip (Kirkpatrick, Gelatt and V ecchi 1983).。

DSP滤波器中英文对照外文翻译文献

DSP滤波器中英文对照外文翻译文献

中英文对照外文翻译文献(文档含英文原文和中文翻译)译文:GA算法优化IIR滤波器的设计摘要本文提出了运用遗传算法(GA)来优化无限脉冲响应数字滤波器(IIR)的设计。

IIR滤波器本质上是一个递归响应的数字滤波器。

由于IIR 数字滤波器的表面误差通常是非线性的和多峰的，而全局优化技术需要避免局部最小值。

本文提出了启发式方式来设计IIR滤波器。

GA是组合优化问题中一种功能强大的全局优化算法，该论文发现IIR数字滤波器的最佳系数可以通过GA 优化。

该设计提出低通和高通IIR数字滤波器的设计，以提供过渡频带的估计值。

结果发现，所计算出的值比可用于过滤器的在MATLAB设计FDA工具更优化。

举个例子，采用的仿真结果表明在过渡带和均方误差(MSE)的改善。

零极点的位置也被提出来用来描述系统的的稳定性，以便将结果与模拟退火(SA)的方法相比较。

关键词：数字滤波器;无限冲激响应(IIR);遗传算法(GA);优化1.说明在过去的几十年中的数字信号处理(DSP)领域已经成长太重要的理论和技术。

在DSP中，有两个重要的类型系统。

第一类型的系统是执行信号滤波的时域，因此它被称为数字滤波器。

第二类型的系统提供的信号表示频域，被称为频谱分析仪。

数字滤波是DSP的最有力的工具之一。

数字滤波器能够性能规格，最好的同时也是极其困难的，而且不可能的是，先用模拟滤波器实现。

另外，数字滤波器的特性，可以很容易地在软件控制下发生变化。

数字滤波器被分类为有限持续时间脉冲响应(FIR)滤波器或无限持续时间脉冲响应(IIR)滤波器，这取决于该系统的脉冲响应的形式。

在FIR系统中，脉冲响应序列是有限的持续时间，即，它具有非零项的数量有限。

数字无限脉冲响应(IIR)滤波器通常可以提供比其等效有限脉冲响应(FIR)滤波器更好的性能和更少的计算成本，并已成为越来越感兴趣的目标。

但是，由于IIR滤波器的误差表面通常是非线性的，多式联运，传统的基于梯度的设计方法可以很容易地陷入错误的表面。