ORIGINAL ARTICLE Full-class set classification using the Hungarian algorithm Ludmila I. Kuncheva Received: 23 March 2010 / Accepted: 23 June 2010 / Published online: 16 September 2010 C211 Springer-Verlag 2010 Abstract Consider a set-classification task where c objects must be labelled simultaneously in c classes, knowing that there is only one object coming from each class (full-class set). Such problems may occur in auto- matic attendance registration systems, simultaneous tracking of fast moving objects and more. A Bayes-optimal solution
to the full-class set classification problem is pro- posed using a single classifier and the Hungarian assign- ment algorithm. The advantage of set classification over individually based classification is demonstrated both the- oretically and experimentally, using simulated, benchmark and real data. Keywords Full-class set classification C1 Bayes-optimal classifier C1 Label assignment problem 1 Introduction For many years now, pattern recognition and machine learning have devoted major efforts to improving classifi- cation accuracy, and have allegedly cast aside a number of challenges arising from real-life problems [7]. One of the standard assumptions in classical pattern recognition is that the data comes as an independent identically distributed (i.i.d) sequence of instances. Here we abandon this assumption and consider dependent data where a set of instances has to be classified together, knowing that the set contains at most one instance from each class (or exactly one instance from each class, if the cardinality of the set equals the number of classes). Consider an automatic sys- tem that uses face recognition to record students’ atten- dance of a lesson against a predefined list of identities. Without enforcing the one-to-one correspondence, one identity may be assigned to two or more students. If the individual face classifier is reasonably correct, then some mistakes can be remedied. In this context, a classifier is informally described as ‘‘reasonably correct’’ if the true class is ranked high among all classes, even when the top ranked class is incorrect. An example of non-i.i.d classification, called the multi- ple-instance problem, arises in complex machine learning applications where the information about the instances is incomplete or ambiguous [4, 11, 17], e.g., in drug activity prediction [4]. The training examples come in ‘‘bags’’ labelled either positive or negative. For a positive bag, it is known that at least one instance in the bag has true positive label. For a bag labelled negative, all instances are known to be negative. The problem is to design a classifier that can label as accurately as possible an unseen bag of instances. Set classification is considered by Ning and Karypis [13], where all the instances in the set to be classified are known to have come from the same class. This problem may arise in face recognition where multiple images of the same person’s face are submitted as a set. Collective rec- ognition is another scenario where a set of instances are labelled together [12, 16]. The...
Website: pages.bangor.ac.uk | Filesize: -
No of Page(s): 9
Download Full-class set classification using the Hungarian algorithm.pdf
Sunday, September 30, 2012
Lecture 14: Topological Sort and Depth-first Search
Problem DFS Topological sort Summary Lecture 14: Topological Sort and Depth-first Search CSC2100 Data Structure Yufei Tao CSE department, CUHK April 8, 2011 Problem DFS Topological sort Summary In this lecture, we will discuss a problem called topological sort. Our solution is based on an algorithm called depth-first search, which is another method for traversing a graph. Problem DFS Topological sort Summary 1 Problem Dag Topological sort 2 DFS Rationale Formal description and analysis 3 Topological sort Algorithm Correctness Problem
DFS Topological sort Summary Dag Directed acyclic graph A directed graph G is a dag (directed acyclic graph) if it does not have any cycle. Example a b c d e f g h i a b c d e f g h i The left graph is a dag, but the right is not. Problem DFS Topological sort Summary Topological sort Topological sort problem Problem (Topological sort) Given a dag G = (V , E), find an ordering of V, such that, for each edge (u, v) ∈ E, u precedes v in the ordering. The ordering is called a topological order. Example a b c d e f g h i A topological order: a, b, c, h, d, g, i, f , e. Another: h, a, b, c, d, g, i, f , e. The result is not unique. Problem DFS Topological sort Summary Rationale Depth-first search Before dealing with the topological sort problem, let us first clarify how to perform a depth-first search (DFS) on a graph. At each vertex v, DFS “eagerly” switches to a neighbor of v (unlike BFS that switches only after having inspected all the neighbors of v), as we will see. Note In the sequel, we will say that vertex v is a neighbor of vertex u, if (u, v) ∈ E, namely, there is an edge from u to v. Problem DFS Topological sort Summary Rationale DFS example Example At the beginning, color all vertices white (which means “not visited yet”). Consider a DFS starting from vertex c. a b c d e f g h i Color c as grey (which means “visited, but neighbors not finished yet”). Switch to a white neighbor of c, say e. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example a b c d e f g h i Color e grey. Attempt to switch to a white neighbor of e. As such a neighbor does not exist, color e black (which means “visited, and all neighbors done”). The algorithm then backtracks to c. At c, switch to the next white neighbor of c, i.e., d. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example a b c d e f g h i Color d grey. Switch to a white neighbor of d, i.e., g. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example Access g: Access f :...
Website: www.cse.cuhk.edu.hk | Filesize: -
No of Page(s): 17
Download Lecture 14: Topological Sort and Depth-first Search - CSC2100 Data ....pdf
DFS Topological sort Summary Dag Directed acyclic graph A directed graph G is a dag (directed acyclic graph) if it does not have any cycle. Example a b c d e f g h i a b c d e f g h i The left graph is a dag, but the right is not. Problem DFS Topological sort Summary Topological sort Topological sort problem Problem (Topological sort) Given a dag G = (V , E), find an ordering of V, such that, for each edge (u, v) ∈ E, u precedes v in the ordering. The ordering is called a topological order. Example a b c d e f g h i A topological order: a, b, c, h, d, g, i, f , e. Another: h, a, b, c, d, g, i, f , e. The result is not unique. Problem DFS Topological sort Summary Rationale Depth-first search Before dealing with the topological sort problem, let us first clarify how to perform a depth-first search (DFS) on a graph. At each vertex v, DFS “eagerly” switches to a neighbor of v (unlike BFS that switches only after having inspected all the neighbors of v), as we will see. Note In the sequel, we will say that vertex v is a neighbor of vertex u, if (u, v) ∈ E, namely, there is an edge from u to v. Problem DFS Topological sort Summary Rationale DFS example Example At the beginning, color all vertices white (which means “not visited yet”). Consider a DFS starting from vertex c. a b c d e f g h i Color c as grey (which means “visited, but neighbors not finished yet”). Switch to a white neighbor of c, say e. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example a b c d e f g h i Color e grey. Attempt to switch to a white neighbor of e. As such a neighbor does not exist, color e black (which means “visited, and all neighbors done”). The algorithm then backtracks to c. At c, switch to the next white neighbor of c, i.e., d. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example a b c d e f g h i Color d grey. Switch to a white neighbor of d, i.e., g. Problem DFS Topological sort Summary Rationale DFS example (cont.) Example Access g: Access f :...
Website: www.cse.cuhk.edu.hk | Filesize: -
No of Page(s): 17
Download Lecture 14: Topological Sort and Depth-first Search - CSC2100 Data ....pdf
Average-Case Analysis of Incremental Topological Ordering
Average-Case Analysis of Incremental Topological Ordering Deepak Ajwani Tobias Friedrich Abstract Many applications like pointer analysis and incremental compilation require maintaining a topological ordering of the nodes of a directed acyclic graph (DAG) under dynamic up- dates. All known algorithms for this problem are either only analyzed for worst-case insertion sequences or only evaluated experimentally on random DAGs. We present the first average- case analysis of incremental topological ordering algorithms. We prove an expected runtime of u1D4AA(u1D45B2 polylog(u1D45B)) under insertion
of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). 1 Introduction There has been a growing interest in dynamic graph algorithms over the last two decades due to their applications in a variety of contexts including operating systems, information systems, net- work management, assembly planning, VLSI design and graphical applications. Typical dynamic graph algorithms maintain a certain property (e.g., connectivity information) of a graph that changes (a new edge inserted or an existing edge deleted) dynamically over time. An algorithm or a problem is called fully dynamic if both edge insertions and deletions are allowed, and it is called partially dynamic if only one (either only insertion or only deletion) is allowed. If only insertions are allowed, the partially dynamic algorithm is called incremental; if only deletions are allowed, it is called decremental. While a number of fully dynamic algorithms have been obtained for various properties on undirected graphs (see [13] and references therein), the design and analysis of fully dynamic algorithms for directed graphs have turned out to be much harder (e.g., [16, 27–29]). Much of the research on directed graphs is therefore concentrated on the design of partially dy- namic algorithms instead (e.g., [5, 10, 18]). In this paper, we focus on the analysis of algorithms for maintaining a topological ordering of directed graphs in an incremental setting. For a directed graph u1D43A = (u1D449,u1D438) (with u1D45B := ∣u1D449∣ and u1D45A := ∣u1D438∣), a topological order u1D447 : u1D449 → [1..u1D45B] is a linear ordering of its nodes such that for all directed paths from u1D465 ∈ u1D449 to u1D466 ∈ u1D449 (u1D465 ∕= u1D466), it holds that u1D447(u1D465) < u1D447(u1D466). A directed graph has a topological ordering if and only if it is acyclic. There are well-known algorithms for computing the topological ordering of a directed acyclic graph (DAG) in u1D4AA(u1D45A+u1D45B) time in an offline setting (see e.g. [11]). In a fully dynamic setting, each time an edge is added or deleted from the DAG, we are required to update the bijective mapping u1D447. In the online/incremental variant of this problem, the edges of the DAG are not known in advance but are inserted one at a time (no deletions allowed). As the topological order remains valid when removing edges, most algorithms for online topological...
Website: www.mpi-inf.mpg.de | Filesize: -
No of Page(s): 14
Download Average-Case Analysis of Incremental Topological Ordering.pdf
of the edges of a complete DAG in a random order for the algorithms of Alpern et al. (SODA, 1990), Katriel and Bodlaender (TALG, 2006), and Pearce and Kelly (JEA, 2006). 1 Introduction There has been a growing interest in dynamic graph algorithms over the last two decades due to their applications in a variety of contexts including operating systems, information systems, net- work management, assembly planning, VLSI design and graphical applications. Typical dynamic graph algorithms maintain a certain property (e.g., connectivity information) of a graph that changes (a new edge inserted or an existing edge deleted) dynamically over time. An algorithm or a problem is called fully dynamic if both edge insertions and deletions are allowed, and it is called partially dynamic if only one (either only insertion or only deletion) is allowed. If only insertions are allowed, the partially dynamic algorithm is called incremental; if only deletions are allowed, it is called decremental. While a number of fully dynamic algorithms have been obtained for various properties on undirected graphs (see [13] and references therein), the design and analysis of fully dynamic algorithms for directed graphs have turned out to be much harder (e.g., [16, 27–29]). Much of the research on directed graphs is therefore concentrated on the design of partially dy- namic algorithms instead (e.g., [5, 10, 18]). In this paper, we focus on the analysis of algorithms for maintaining a topological ordering of directed graphs in an incremental setting. For a directed graph u1D43A = (u1D449,u1D438) (with u1D45B := ∣u1D449∣ and u1D45A := ∣u1D438∣), a topological order u1D447 : u1D449 → [1..u1D45B] is a linear ordering of its nodes such that for all directed paths from u1D465 ∈ u1D449 to u1D466 ∈ u1D449 (u1D465 ∕= u1D466), it holds that u1D447(u1D465) < u1D447(u1D466). A directed graph has a topological ordering if and only if it is acyclic. There are well-known algorithms for computing the topological ordering of a directed acyclic graph (DAG) in u1D4AA(u1D45A+u1D45B) time in an offline setting (see e.g. [11]). In a fully dynamic setting, each time an edge is added or deleted from the DAG, we are required to update the bijective mapping u1D447. In the online/incremental variant of this problem, the edges of the DAG are not known in advance but are inserted one at a time (no deletions allowed). As the topological order remains valid when removing edges, most algorithms for online topological...
Website: www.mpi-inf.mpg.de | Filesize: -
No of Page(s): 14
Download Average-Case Analysis of Incremental Topological Ordering.pdf
Notes on Graph Algorithms Used in Optimizing Compilers
Notes on Graph Algorithms Used in Optimizing Compilers Carl D. Offner University of Massachusetts Boston April 26, 2011 Contents 1 Depth-First Walks 1 1.1 Depth-First Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 A Characterization of DAGS . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 A Characterization of Descendants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 The Path Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 An Application: Strongly Connected Components . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Tarjan’s Original Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Flow Graphs 19 2.1 Flow Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Dominators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Depth-First Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Reducible Flow Graphs 24 3.1 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Algorithms for Constructing Intervals . . . ....
Website: www.cs.umb.edu | Filesize: -
No of Page(s): 100
Download Notes on Graph Algorithms Used in Optimizing Compilers.pdf
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 A Characterization of Descendants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.4 The Path Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.5 An Application: Strongly Connected Components . . . . . . . . . . . . . . . . . . . . . . . . 11 1.6 Tarjan’s Original Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2 Flow Graphs 19 2.1 Flow Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2 Dominators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 2.3 Depth-First Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3 Reducible Flow Graphs 24 3.1 Intervals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.2 Algorithms for Constructing Intervals . . . ....
Website: www.cs.umb.edu | Filesize: -
No of Page(s): 100
Download Notes on Graph Algorithms Used in Optimizing Compilers.pdf
Improved force-directed layouts - Graphviz
Techniques for drawing graphs based on force-directed place- ment and virtual physical models have proven surprisingly successful in producing good layouts of undirected graphs. Aspects of symmetry, structure, clustering and reasonable vertex distribution arise from initial, formless clouds ofpoints. However,when nodes must be labeled and point vertices are replaced by non-pointvertices, simple force-directed models produce unreadable drawings,
even for a moderate number of nodes. This paper describes the application of two post-processing techniques that can be applied to any initial vertex layout to produce uncluttered layouts with non-point nodes. 1 Introduction In general, drawing undirected graphs is problematic. The di#0Eculty lies in there being too much freedom. If structure is imposed on the graph, workable tech- niques arise. For example, if the graph is interpreted to have a directed #0Dow, one canemploythe Sugiyama-stylealgorithms#5B25,12#5D.Alternatively,one can suitably restrict the layout style in order to get a handle on the problem. As an example here, we can consider the class of orthogonal layouts, for which a collection of well-developed and analyzed algorithms is available#5B26,27,8#5D. But without us- ing such restrictions, there is, at present, no simple non-heuristic algorithm for e#0Eciently drawing general undirected graphs. The most e#0Bective techniques for handling undirected graphs are based on virtual physical models. These techniques, going back to Eades#5B6#5D and, compu- tationally, to Kruskal#5B17#5D, represent the vertices of a graph as physical objects subject to various forces, natural and unnatural. Some subset of the forces en- codes the edge informationof the graph, typically as an attractive force between the two endpoints of the edge. The object then becomes one of repositioning the nodes in order to minimize the energy of the system or to achieve a stable con#0Cguration vis-a-vis the forces acting on the particles. Standard techniques, such as steepest descent or discrete iteration, can be used to search for the de- sired con#0Cguration,although there is always the possibilityof only #0Cnding a local minimum.Once the #0Cnal node positions are determined, the drawing is typically completed by connecting edge endpoints with line segments. In practice, these layout methods are remarkably good, especially given the naive nature of the algorithms #28cf. #5B18,7#5D#29. The resulting drawings typically cap- ture many symmetries of the graph, while avoiding the expensive computations 2 Marden ldt kg hg ggt Epstein kt Freedman ds Milnor cd Thurston vd Douady Hubard fg Mandelbrot Mumford Conway lat cg Tarjan Cannon crys gcv Almgren Dobkin Chazelle cv Taylor fd Peskin sg Wilks gv dv Fig.1. The e#0Bect of non-point nodes involved in explicitly looking for symmetries#5B19#5D. In addition, these methods identify signi#0Ccant clusters of nodes while producing a reasonable distribution of the nodes. There has been a varietyofwork on this class of algorithms#5B14, 10,4,9,24,2,15,13,3#5D, leading to some quite e#0Ecient algorithmsthat can handle #5Cmedium-sized" graphs. Despite the...
Website: www.graphviz.org | Filesize: -
No of Page(s): 10
Download Improved force-directed layouts - Graphviz.pdf
even for a moderate number of nodes. This paper describes the application of two post-processing techniques that can be applied to any initial vertex layout to produce uncluttered layouts with non-point nodes. 1 Introduction In general, drawing undirected graphs is problematic. The di#0Eculty lies in there being too much freedom. If structure is imposed on the graph, workable tech- niques arise. For example, if the graph is interpreted to have a directed #0Dow, one canemploythe Sugiyama-stylealgorithms#5B25,12#5D.Alternatively,one can suitably restrict the layout style in order to get a handle on the problem. As an example here, we can consider the class of orthogonal layouts, for which a collection of well-developed and analyzed algorithms is available#5B26,27,8#5D. But without us- ing such restrictions, there is, at present, no simple non-heuristic algorithm for e#0Eciently drawing general undirected graphs. The most e#0Bective techniques for handling undirected graphs are based on virtual physical models. These techniques, going back to Eades#5B6#5D and, compu- tationally, to Kruskal#5B17#5D, represent the vertices of a graph as physical objects subject to various forces, natural and unnatural. Some subset of the forces en- codes the edge informationof the graph, typically as an attractive force between the two endpoints of the edge. The object then becomes one of repositioning the nodes in order to minimize the energy of the system or to achieve a stable con#0Cguration vis-a-vis the forces acting on the particles. Standard techniques, such as steepest descent or discrete iteration, can be used to search for the de- sired con#0Cguration,although there is always the possibilityof only #0Cnding a local minimum.Once the #0Cnal node positions are determined, the drawing is typically completed by connecting edge endpoints with line segments. In practice, these layout methods are remarkably good, especially given the naive nature of the algorithms #28cf. #5B18,7#5D#29. The resulting drawings typically cap- ture many symmetries of the graph, while avoiding the expensive computations 2 Marden ldt kg hg ggt Epstein kt Freedman ds Milnor cd Thurston vd Douady Hubard fg Mandelbrot Mumford Conway lat cg Tarjan Cannon crys gcv Almgren Dobkin Chazelle cv Taylor fd Peskin sg Wilks gv dv Fig.1. The e#0Bect of non-point nodes involved in explicitly looking for symmetries#5B19#5D. In addition, these methods identify signi#0Ccant clusters of nodes while producing a reasonable distribution of the nodes. There has been a varietyofwork on this class of algorithms#5B14, 10,4,9,24,2,15,13,3#5D, leading to some quite e#0Ecient algorithmsthat can handle #5Cmedium-sized" graphs. Despite the...
Website: www.graphviz.org | Filesize: -
No of Page(s): 10
Download Improved force-directed layouts - Graphviz.pdf
Intelligent Controller for Mobile Robot: Fuzzy Logic Approach
A key issue in the research of an autonomous mobile robot is the design and development of an intelligent controller which can control and enables the robot to navigate in a real world environment, avoiding structured and unstructured obstacles especially in crowded and unpredictably changing environment, whether it is in land, underground, under water, on
the air or in space. An intelligent system has the ability to act appropriately in an uncertain environment, where an appropriate action is that which increases the probability of success, and success is the achievement of behavioral sub goals that support the system's ultimate goal. This paper presents the development in the area of intelligent controller for mobile robot in various (known and unknown) environments. A successful way of structuring the navigation task deal with the issues of individual behaviour design and action coordination. The behaviours will be addressed using fuzzy logic in the present research. The inputs to the proposed fuzzy control scheme consist of a heading angle between a robot and a specified target and the distances between the robot and the obstacles to the left, front, and right to its locations, being acquired by an array of sensors. In this paper, we proposed an intelligent controller for mobile robot navigation algorithm employing fuzzy theory in a complex cluttered environment. Simulation results verified the effectiveness of the controllers. 1 Introduction Current research and development of mobile robot have attracted the attention of researchers in the areas of engineering, computer science, biology, mining and others. This is due to the high potential of mobile robots application. Autonomous mobile robots are robots which can perform desired tasks in unstructured environments without continuous human guidance (Frank and Goswami, 2004; Ibrahim and Fernandes, 2004; Kim and Cho, 2006; Waterman, 1989). Many kinds of robots are autonomous to some degree. One important area of current robotics research is to enable the robot to cope with its environment whether this is on land, underwater, in the air, underground or in space. A fully autonomous robot in the real world has the ability to: • Gain information about the environment. • Travel from one point to another point, without human navigation assistance. • Avoid situations that are harmful to people, property or itself. • Repair itself without outside assistance. A robot may also be able to learn autonomously. Autonomous learning includes the ability to: • Learn or gain new capabilities without outside assistance. • Adjust strategies based on the surroundings. • Adapt to surroundings without outside assistance. Navigation for mobile robots can be well-defined in mathematical (geometrical) terms. It also involved many distinct sensory inputs and computational processes. Elementary decisions like turn left, or turn right, or run or stop is made on the basis...
Website: www.civil.iitb.ac.in | Filesize: -
No of Page(s): 8
Download Intelligent Controller for Mobile Robot: Fuzzy Logic Approach.pdf
the air or in space. An intelligent system has the ability to act appropriately in an uncertain environment, where an appropriate action is that which increases the probability of success, and success is the achievement of behavioral sub goals that support the system's ultimate goal. This paper presents the development in the area of intelligent controller for mobile robot in various (known and unknown) environments. A successful way of structuring the navigation task deal with the issues of individual behaviour design and action coordination. The behaviours will be addressed using fuzzy logic in the present research. The inputs to the proposed fuzzy control scheme consist of a heading angle between a robot and a specified target and the distances between the robot and the obstacles to the left, front, and right to its locations, being acquired by an array of sensors. In this paper, we proposed an intelligent controller for mobile robot navigation algorithm employing fuzzy theory in a complex cluttered environment. Simulation results verified the effectiveness of the controllers. 1 Introduction Current research and development of mobile robot have attracted the attention of researchers in the areas of engineering, computer science, biology, mining and others. This is due to the high potential of mobile robots application. Autonomous mobile robots are robots which can perform desired tasks in unstructured environments without continuous human guidance (Frank and Goswami, 2004; Ibrahim and Fernandes, 2004; Kim and Cho, 2006; Waterman, 1989). Many kinds of robots are autonomous to some degree. One important area of current robotics research is to enable the robot to cope with its environment whether this is on land, underwater, in the air, underground or in space. A fully autonomous robot in the real world has the ability to: • Gain information about the environment. • Travel from one point to another point, without human navigation assistance. • Avoid situations that are harmful to people, property or itself. • Repair itself without outside assistance. A robot may also be able to learn autonomously. Autonomous learning includes the ability to: • Learn or gain new capabilities without outside assistance. • Adjust strategies based on the surroundings. • Adapt to surroundings without outside assistance. Navigation for mobile robots can be well-defined in mathematical (geometrical) terms. It also involved many distinct sensory inputs and computational processes. Elementary decisions like turn left, or turn right, or run or stop is made on the basis...
Website: www.civil.iitb.ac.in | Filesize: -
No of Page(s): 8
Download Intelligent Controller for Mobile Robot: Fuzzy Logic Approach.pdf
A Fast Elitist Non-Dominated Sorting Genetic Algorithm
Multi-objective evolutionary algorithms which use non-dominated sorting and sharing have been mainly criticized for their (i) a2a4a3a6a5a8a7a10a9a12a11 computational complexity (where a5 is the number of objectives and a7 is the population size), (ii) non-elitism approach, and (iii) the need for specifying a sharing parameter. In this paper, we suggest a non-dominated sorting based multi-objective evolutionary algorithm (we called it the Non-dominated Sorting GA-II or NSGA-II) which alleviates all the above three difficulties. Specifically,
a fast non-dominated sorting approach with a2a4a3a6a5a8a7a14a13a15a11 computational complexity is presented. Second, a selection operator is presented which creates a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) a7 solutions. Simulation results on five difficult test problems show that the proposed NSGA-II is able to find much better spread of solutions in all problems compared to PAES—another elitist multi-objective EA which pays special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II’s low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come. 1 Introduction Over the past decade, a number of multi-objective evolutionary algorithms (MOEAs) have been suggested [9, 3, 5, 13]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single run. Since the principal reason why a problem has a multi-objective formulation is because it is not possible to have a single solution which simultaneously optimizes all objectives, an algorithm that gives a large number of alternative solutions lying on or near the Pareto-optimal front is of great practical value. The Non-dominated Sorting Genetic Algorithm (NSGA) proposed in Srinivas and Deb [9] was one of the first such evolutionary algorithms. Over the years, the main criticism of the NSGA approach have been as follows: High computational complexity of non-dominated sorting: The non-dominated sorting algorithm in use uptil now is a16a8a17a19a18a21a20a23a22a12a24 which in case of large population sizes 2 Deb, Agrawal, Pratap, and Meyarivan is very expensive, especially since the population needs to be sorted in every gen- eration. Lack of elitism: Recent results [12, 8] show clearly that elitism can speed up the performance of the GA significantly, also it helps to prevent the loss of good solutions once they have been found. Need for specifying the sharing parameter a25a27a26a29a28a31a30a15a32a34a33 : Traditional mechanisms of insuring diversity in a population so as to get a wide variety of equivalent solutions have relied heavily on the concept of sharing. The main problem with sharing is that it requires the specification of a sharing parameter (a25 a26a29a28a31a30a15a32a35a33 ). Though there has been some work on dynamic sizing of the sharing parameter [4], a parameterless diversity preservation mechanism is desirable. In this paper, we address all of these issues and propose a much improved version of NSGA which...
Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 11
Download A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi ....pdf
a fast non-dominated sorting approach with a2a4a3a6a5a8a7a14a13a15a11 computational complexity is presented. Second, a selection operator is presented which creates a mating pool by combining the parent and child populations and selecting the best (with respect to fitness and spread) a7 solutions. Simulation results on five difficult test problems show that the proposed NSGA-II is able to find much better spread of solutions in all problems compared to PAES—another elitist multi-objective EA which pays special attention towards creating a diverse Pareto-optimal front. Because of NSGA-II’s low computational requirements, elitist approach, and parameter-less sharing approach, NSGA-II should find increasing applications in the years to come. 1 Introduction Over the past decade, a number of multi-objective evolutionary algorithms (MOEAs) have been suggested [9, 3, 5, 13]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single run. Since the principal reason why a problem has a multi-objective formulation is because it is not possible to have a single solution which simultaneously optimizes all objectives, an algorithm that gives a large number of alternative solutions lying on or near the Pareto-optimal front is of great practical value. The Non-dominated Sorting Genetic Algorithm (NSGA) proposed in Srinivas and Deb [9] was one of the first such evolutionary algorithms. Over the years, the main criticism of the NSGA approach have been as follows: High computational complexity of non-dominated sorting: The non-dominated sorting algorithm in use uptil now is a16a8a17a19a18a21a20a23a22a12a24 which in case of large population sizes 2 Deb, Agrawal, Pratap, and Meyarivan is very expensive, especially since the population needs to be sorted in every gen- eration. Lack of elitism: Recent results [12, 8] show clearly that elitism can speed up the performance of the GA significantly, also it helps to prevent the loss of good solutions once they have been found. Need for specifying the sharing parameter a25a27a26a29a28a31a30a15a32a34a33 : Traditional mechanisms of insuring diversity in a population so as to get a wide variety of equivalent solutions have relied heavily on the concept of sharing. The main problem with sharing is that it requires the specification of a sharing parameter (a25 a26a29a28a31a30a15a32a35a33 ). Though there has been some work on dynamic sizing of the sharing parameter [4], a parameterless diversity preservation mechanism is desirable. In this paper, we address all of these issues and propose a much improved version of NSGA which...
Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 11
Download A Fast Elitist Non-Dominated Sorting Genetic Algorithm for Multi ....pdf
Saturday, September 29, 2012
Sensor Deployment and Target Localization Based on Virtual Forces
Sensor Deployment and Target Localization Based on Virtual Forces Yi Zou and Krishnendu Chakrabarty Abstract— The effectiveness of cluster-based distributed sensor networks depends to a large extent on the coverage provided by the sensor deployment. We propose a virtual force algorithm (VFA) as a sensor deployment strategy to enhance the coverage after an initial random placement of sensors. For a given number of sensors, the VFA algorithm attempts to maximize the sensor field coverage. A judicious combination of attractive andrepulsive forces is used to determine virtual motion paths and the rate of movement for the randomly-placed sensors. Once the effective sensor positions are identified, a one-time movement with energy consideration incorporated is carried out, i.e., the sensors are redeployed to these positions. We also propose a novel probabilistic target localization algorithm that is executed by the cluster head. The localization results are used by the cluster head to query only a few sensors (out of those that report the presence of a target) for more detailed information. Simulation results are presented to demonstrate the effectiveness of the proposed approach. Index Terms— Sensor coverage, distributed sensor networks, sensor placement, virtual force, localization. I. INTRODUCTION Distributed sensor networks (DSNs) are important for a number of strategic applications such as coordinated target detection, surveillance, and localization. The effectiveness of DSNs is determined to a large extent by the coverage provided by the sensor deployment. The positioning of sensors affects coverage, communication cost, and resource management. In this paper, we focus on sensor placement strategies that maximize the coverage for a given number of sensors within a cluster in cluster-based DSNs. As an initial deployment step, a random placement of sensors in the target area (sensor field) is often desirable, especially if no aprioriknowledge of the terrain is available. Random deployment is also practical in military applications, where DSNs are initially established by dropping or throwing sensors into the sensor field. However, random deployment does not always lead to effective coverage, especially if the sensors are overly clustered and there is a small concentration of sensors in certain parts of the sensor field. The key idea of this paper is that the coverage provided by a random deployment can be improved using a force-directed algorithm. Y. Zou and K. Chakrabarty are with the Department of Electrical and Computer Engineering, Duke University, Durham, NC 27708, USA. E-mail: {yz1, krish}@ee.duke.edu. This research was supported in part by ONR under grant no. N66001- 00-1-8946. It was also sponsored in part by DARPA, and administered by the Army Research Office under Emergent Surveillance Plexus MURI Award No. DAAD19-01-1-0504. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the views of the sponsoring agencies. We present the virtual force algorithm (VFA) as a sensor deployment strategy to enhance the coverage after an initial random placement of...
Website: www.ieee-infocom.org | Filesize: -
No of Page(s): 11
Download Sensor Deployment and Target Localization Based on Virtual Forces.pdf
ImPrEd: An Improved Force-Directed Algorithm
An Improved Force-Directed Algorithm that Prevents Nodes from Crossing Edges Paolo Simonetto1, Daniel Archambault2, David Auber1, and Romain Bourqui1 1LaBRI, Université Bordeaux 1 — INRIA, Bordeaux Sud-Ouest 2University College Dublin Abstract PrEd [Ber00] is a force-directed algorithm that improves the existing layout of a graph while preserving its edge crossing properties. The algorithm has
a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly- restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundar- ies. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd. Categories and Subject Descriptors (according to ACM CCS): G.2.2 [Discrete Mathematics]: Graph Theory—Graph Algorithms 1. Introduction PrEd [Ber00] is a force-directed algorithm [Ead84, FR91] that preserves the edge crossing properties of an input layout. The algorithm computes the maximal displacement of nodes and restricts their movement to guarantee this property. The author of PrEd suggested two possible applications: improving the layout [Pur97] of planar, straight-line graph drawing algorithms [DFPP90] and driving force-directed graph layout interactively. By realising that not only does PrEd preserve all edge crossings in an existing layout but actually prevents nodes from crossing edges, we can apply this algorithm to a wider range of problems beyond those stated in the original paper. For example, PrEd can be used to improve Euler-like diagrams [SAA09] where nodes are set elements and edges are set boundaries. In general, we can use PrEd for tasks where we would like to bound portions of a layout, extending the applicability beyond “preserving edge crossing properties” [Ber00]. The contribution of this paper is ImPrEd: an improved force-directed algorithm that prevents nodes from crossing edges. ImPrEd is faster than PrEd and grants greater out- put control. Our test cases provide some evidence that it has improved visual quality. The modifications made, initially motivated by the problem of drawing Euler-like diagrams, can also be useful for general graph drawing. 2. Previous and Related Work Many approaches aim to constrain or restrict node move- ment in force-directed algorithms. Mental map preservation techniques, described in Section 2.1, restrict node...
Website: hal.inria.fr | Filesize: -
No of Page(s): 10
Download ImPrEd: An Improved Force-Directed Algorithm that ... - HAL-Inria.pdf
a number of applications including: improving the layouts of planar graph drawing algorithms, interacting with a graph layout, and drawing Euler-like diagrams. The algorithm ensures that nodes do not cross edges during its execution. However, PrEd can be computationally expensive and overly- restrictive in terms of node movement. In this paper, we introduce ImPrEd: an improved version of PrEd that overcomes some of its limitations and widens its range of applicability. ImPrEd also adds features such as flexible or crossable edges, allowing for greater control over the output. Flexible edges, in particular, can improve the distribution of graph elements and the angular resolution of the input graph. They can also be used to generate Euler diagrams with smooth boundar- ies. As flexible edges increase data set size, we experience an execution/drawing quality trade off. However, when flexible edges are not used, ImPrEd proves to be consistently faster than PrEd. Categories and Subject Descriptors (according to ACM CCS): G.2.2 [Discrete Mathematics]: Graph Theory—Graph Algorithms 1. Introduction PrEd [Ber00] is a force-directed algorithm [Ead84, FR91] that preserves the edge crossing properties of an input layout. The algorithm computes the maximal displacement of nodes and restricts their movement to guarantee this property. The author of PrEd suggested two possible applications: improving the layout [Pur97] of planar, straight-line graph drawing algorithms [DFPP90] and driving force-directed graph layout interactively. By realising that not only does PrEd preserve all edge crossings in an existing layout but actually prevents nodes from crossing edges, we can apply this algorithm to a wider range of problems beyond those stated in the original paper. For example, PrEd can be used to improve Euler-like diagrams [SAA09] where nodes are set elements and edges are set boundaries. In general, we can use PrEd for tasks where we would like to bound portions of a layout, extending the applicability beyond “preserving edge crossing properties” [Ber00]. The contribution of this paper is ImPrEd: an improved force-directed algorithm that prevents nodes from crossing edges. ImPrEd is faster than PrEd and grants greater out- put control. Our test cases provide some evidence that it has improved visual quality. The modifications made, initially motivated by the problem of drawing Euler-like diagrams, can also be useful for general graph drawing. 2. Previous and Related Work Many approaches aim to constrain or restrict node move- ment in force-directed algorithms. Mental map preservation techniques, described in Section 2.1, restrict node...
Website: hal.inria.fr | Filesize: -
No of Page(s): 10
Download ImPrEd: An Improved Force-Directed Algorithm that ... - HAL-Inria.pdf
Operation Scheduling: Algorithms and Applications
Operation scheduling (OS) is an important task in the high-level synthe- sis process. An inappropriate scheduling of the operations can fail to exploit the full potential of the system. In this chapter, we try to give a comprehensive cov- erage on the heuristic algorithms currently available for solving both timing and resource constrained scheduling problems. Besides providing a broad survey on this topic, we focus
on some of the most popularly used algorithms, such as List Scheduling, Force-Directed Scheduling and Simulated Annealing, as well as the newly introduced approach based on the Ant Colony Optimization meta-heuristics. We discuss in details on their applicability and performance by comparing them on solution quality,performancestability, scalability, extensibility,and computation cost. Moreover,as an application of operation scheduling,we introduce a novel uni- formed design space exploration method that exploits the duality of the time and resource constrained scheduling problems, which automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. Keywords: Design space exploration, Ant colony optimization, Instruction scheduling, MAX–MIN ant system 13.1 Introduction As fabrication technology advances and transistors become more plentiful, modern computingsystemscanachievebettersystemperformancebyincreasingthe amount ofcomputationunits.It is estimatedthatwe will be ableto integratemorethana half billion transistors on a 468mm 2 chip by the year of 2009 [38]. This yields tremen- dous potential for future computing systems, however, it imposes big challenges on how to effectively use and design such complicated systems. As computing systems become more complex, so do the applications that can run on them. Designers will increasingly rely on automated design tools in order P. Coussy and A. Morawiec (eds.) High-Level Synthesis. c©Springer Science + Business Media B.V. 2008 231 232 G. Wang et al. to map applications onto these systems. One fundamental process of these tools is mapping a behavioral application specification to the computing system. For exam- ple, the tool may take a C functionand create the code to programa microprocessor. This is viewed as software compilation. Or the tool may take a transaction level behavior and create a register transfer level (RTL) circuit description. This is called hardware or behavioral synthesis [31]. Both software and hardware synthesis flows are essential for the use and design of future computing systems. Operation scheduling (OS) is an important problem in software compilation and hardwaresynthesis. An inappropriateschedulingofthe operationscan fail to exploit the full potential of the system. Operation scheduling appears in a number of dif- ferent problems, e.g., compiler design for superscalar and VLIW microprocessors [23], distributed clustering computation architectures [4] and behavioral synthesis of ASICs and FPGAs [31]. Operationschedulingis performedona behavioraldescriptionofthe application. Thisdescriptionistypicallydecomposedintoseveralblocks(e.g.,basic blocks),and each of the blocks is represented by a data flow graph (DFG). Operation scheduling can be classified as resource constrained or timing con- strained. Given a DFG, clock cycle time, resource count and resource delays, a resource constrained scheduling finds the minimum number...
Website: cseweb.ucsd.edu | Filesize: -
No of Page(s): 25
Download Operation Scheduling: Algorithms and Applications.pdf
on some of the most popularly used algorithms, such as List Scheduling, Force-Directed Scheduling and Simulated Annealing, as well as the newly introduced approach based on the Ant Colony Optimization meta-heuristics. We discuss in details on their applicability and performance by comparing them on solution quality,performancestability, scalability, extensibility,and computation cost. Moreover,as an application of operation scheduling,we introduce a novel uni- formed design space exploration method that exploits the duality of the time and resource constrained scheduling problems, which automatically constructs a high quality time/area tradeoff curve in a fast, effective manner. Keywords: Design space exploration, Ant colony optimization, Instruction scheduling, MAX–MIN ant system 13.1 Introduction As fabrication technology advances and transistors become more plentiful, modern computingsystemscanachievebettersystemperformancebyincreasingthe amount ofcomputationunits.It is estimatedthatwe will be ableto integratemorethana half billion transistors on a 468mm 2 chip by the year of 2009 [38]. This yields tremen- dous potential for future computing systems, however, it imposes big challenges on how to effectively use and design such complicated systems. As computing systems become more complex, so do the applications that can run on them. Designers will increasingly rely on automated design tools in order P. Coussy and A. Morawiec (eds.) High-Level Synthesis. c©Springer Science + Business Media B.V. 2008 231 232 G. Wang et al. to map applications onto these systems. One fundamental process of these tools is mapping a behavioral application specification to the computing system. For exam- ple, the tool may take a C functionand create the code to programa microprocessor. This is viewed as software compilation. Or the tool may take a transaction level behavior and create a register transfer level (RTL) circuit description. This is called hardware or behavioral synthesis [31]. Both software and hardware synthesis flows are essential for the use and design of future computing systems. Operation scheduling (OS) is an important problem in software compilation and hardwaresynthesis. An inappropriateschedulingofthe operationscan fail to exploit the full potential of the system. Operation scheduling appears in a number of dif- ferent problems, e.g., compiler design for superscalar and VLIW microprocessors [23], distributed clustering computation architectures [4] and behavioral synthesis of ASICs and FPGAs [31]. Operationschedulingis performedona behavioraldescriptionofthe application. Thisdescriptionistypicallydecomposedintoseveralblocks(e.g.,basic blocks),and each of the blocks is represented by a data flow graph (DFG). Operation scheduling can be classified as resource constrained or timing con- strained. Given a DFG, clock cycle time, resource count and resource delays, a resource constrained scheduling finds the minimum number...
Website: cseweb.ucsd.edu | Filesize: -
No of Page(s): 25
Download Operation Scheduling: Algorithms and Applications.pdf
Fuzzy Logic Control for Robot Maze Traversal
As previously reported, Indiana University South Bend has deployed autonomous robots in their Computer Organization course to facilitate introducing computer science students to the basics of logic, embedded systems, and assembly language. The robots help to provide effective, real-time feedback on program operation and to make assembly language less abstract. As a part of their coursework students are required to program a sensor- based traversal of a maze. This paper details one
solution to this problem employing a fuzzy logic controller to create linguistic rules. Index Terms Fuzzy logic, pedagogy, robots, student projects . INTRODUCTION Assembly language programming in a computer science environment is often taught using abstract exercises to illustrate concepts and encourage student proficiency. To augment this approach we have elected to provide hands-on, real-world experience to our students by introducing robots into our assembly language class. Observing the physical action of robots can generate valuable feedback and have real-world consequences – robots hitting walls make students instantly aware of program errors, for example. It also provides insight into the realities of physical machines such as motor control, sensor calibration, and noise. To help provide a meaningful experience for our computer organization students, we reviewed the course with the following objectives in mind: • Expand the experience of our students in a manner that enhances the student's insight, provides a hands-on, visual, environment for them to learn, and forms an integrated component for future classes. • Remove some of the abstraction inherent in the assembly language class. Specifically, to help enhance the error detection environment. • Provide a kinesthetic aspect to our pedagogy. • Build student expertise early in their program that could lead to research projects and advanced classroom activities later in their program. Specifically, in this case, to build expertise to support later coursework in intelligent systems and robotics. As one component in meeting these objectives we, in cooperation with the Computer Science department, the Intelligent Systems Laboratory, and the University Center for Excellence in Teaching, designed a robotics laboratory to support the assembly language portion of the computer organization class as described in [1]. The balance of this report describes one example project resulting from this environment. Specifically, we describe the results of a student project developing an assembly language fuzzy engine, membership function creation, fuzzy controller, and resulting robot behavior in a Linux-based environment. We also describe subsequent software devlopment in C# under Windows, including graphical membership tuning, real-time display of sensor activation, and fuzzy controller system response. Collectively these tools allow for robust controller development, assembly language support, and an environment suitable for effective classroom and public display. BACKGROUND Robots have long been recognized for their potential educational utility, with examples ranging from abstract, simulated, robots, such as Karel[2] and Turtle[3] for teaching programming and geometry respectively, to competitive events such as robotic soccer...
Website: www.cs.iusb.edu | Filesize: -
No of Page(s): 5
Download Fuzzy Logic Control for Robot Maze Traversal - Computer and ....pdf
solution to this problem employing a fuzzy logic controller to create linguistic rules. Index Terms Fuzzy logic, pedagogy, robots, student projects . INTRODUCTION Assembly language programming in a computer science environment is often taught using abstract exercises to illustrate concepts and encourage student proficiency. To augment this approach we have elected to provide hands-on, real-world experience to our students by introducing robots into our assembly language class. Observing the physical action of robots can generate valuable feedback and have real-world consequences – robots hitting walls make students instantly aware of program errors, for example. It also provides insight into the realities of physical machines such as motor control, sensor calibration, and noise. To help provide a meaningful experience for our computer organization students, we reviewed the course with the following objectives in mind: • Expand the experience of our students in a manner that enhances the student's insight, provides a hands-on, visual, environment for them to learn, and forms an integrated component for future classes. • Remove some of the abstraction inherent in the assembly language class. Specifically, to help enhance the error detection environment. • Provide a kinesthetic aspect to our pedagogy. • Build student expertise early in their program that could lead to research projects and advanced classroom activities later in their program. Specifically, in this case, to build expertise to support later coursework in intelligent systems and robotics. As one component in meeting these objectives we, in cooperation with the Computer Science department, the Intelligent Systems Laboratory, and the University Center for Excellence in Teaching, designed a robotics laboratory to support the assembly language portion of the computer organization class as described in [1]. The balance of this report describes one example project resulting from this environment. Specifically, we describe the results of a student project developing an assembly language fuzzy engine, membership function creation, fuzzy controller, and resulting robot behavior in a Linux-based environment. We also describe subsequent software devlopment in C# under Windows, including graphical membership tuning, real-time display of sensor activation, and fuzzy controller system response. Collectively these tools allow for robust controller development, assembly language support, and an environment suitable for effective classroom and public display. BACKGROUND Robots have long been recognized for their potential educational utility, with examples ranging from abstract, simulated, robots, such as Karel[2] and Turtle[3] for teaching programming and geometry respectively, to competitive events such as robotic soccer...
Website: www.cs.iusb.edu | Filesize: -
No of Page(s): 5
Download Fuzzy Logic Control for Robot Maze Traversal - Computer and ....pdf
Fundamentals of Genetic Algorithms Artificial
RC Chakraborty, www.myreaders.info Fundamentals of Genetic Algorithms : AI Course Lecture 39 – 40, notes, slides www.myreaders.info/ , RC Chakraborty, e-mail rcchak@gmail.com , June 01, 2010 www.myreaders.info/html/artificial_intelligence.html Fundamentals of Genetic Algorithms Artificial Intelligence www.myreaders.info Return to Website Genetic algorithms, topics : Introduction, search optimization algorithm; Evolutionary algorithm (EAs); Genetic Algorithms (GAs) : biological background, search space, working principles, basic genetic algorithm, flow chart for Genetic programming; Encoding : binary encoding, value encoding, permutation encoding, and tree encoding; Operators of genetic
algorithm : reproduction or selection - roulette wheel selection, Boltzmann selection; fitness function; Crossover – one point crossover, two Point crossover, uniform crossover, arithmetic, heuristic; Mutation - flip bit, boundary, non- uniform, uniform, Gaussian; Basic genetic algorithm - solved examples : maximize function f(x) = x 2 and two bar pendulum. RC Chakraborty, www.myreaders.info Fundamentals of Genetic Algorithms Artificial Intelligence Topics (Lectures 39, 40 2 hours) Slides 1. Introduction Why genetic algorithms, Optimization, Search optimization algorithm; Evolutionary algorithm (EAs); Genetic Algorithms (GAs) : Biological background, Search space, Working principles, Basic genetic algorithm, Flow chart for Genetic programming. 03-15 2. Encoding Binary Encoding, Value Encoding, Permutation Encoding, and Tree Encoding. 16-21 3. Operators of Genetic Algorithm Reproduction or selection : Roulette wheel selection, Boltzmann selection; fitness function; Crossover: one-Point crossover, two-Point crossover, uniform crossover, arithmetic, heuristic; Mutation : flip bit, boundary, non-uniform, uniform, Gaussian. 22-35 4. Basic Genetic Algorithm Solved examples : maximize function f(x) = x 2 and two bar pendulum. 36-41 5. References 42 02 RC Chakraborty, www.myreaders.info Fundamentals of Genetic Algorithms What are GAs ? • Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. • Genetic algorithms (GAs) are a part of Evolutionary computing, a rapidly growing area of artificial intelligence. GAs are inspired by Darwin's theory about evolution - "survival of the fittest". • GAs represent an intelligent exploitation of a random search used to solve optimization problems. • GAs, although randomized, exploit historical information to direct the search into the region of better performance within the search space. • In nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones. 03 RC Chakraborty, www.myreaders.info GA - Introduction 1. Introduction to Genetic Algorithms Solving problems mean looking for solutions, which is best among others. Finding the solution to a problem is often thought : − In computer science and AI, as a process of search through the space of possible solutions. The set of possible solutions defines the search space (also called state space) for a given problem. Solutions or partial solutions are viewed as points in the search space. − In engineering and mathematics, as a process of optimization. The problems are first formulated as mathematical models expressed in terms of functions and then to find a solution, discover the parameters that optimize the model or the function components...
Website: www.myreaders.info | Filesize: -
No of Page(s): 42
Download Fundamentals of Genetic Algorithms Artificial ... - Myreaders.info.pdf
algorithm : reproduction or selection - roulette wheel selection, Boltzmann selection; fitness function; Crossover – one point crossover, two Point crossover, uniform crossover, arithmetic, heuristic; Mutation - flip bit, boundary, non- uniform, uniform, Gaussian; Basic genetic algorithm - solved examples : maximize function f(x) = x 2 and two bar pendulum. RC Chakraborty, www.myreaders.info Fundamentals of Genetic Algorithms Artificial Intelligence Topics (Lectures 39, 40 2 hours) Slides 1. Introduction Why genetic algorithms, Optimization, Search optimization algorithm; Evolutionary algorithm (EAs); Genetic Algorithms (GAs) : Biological background, Search space, Working principles, Basic genetic algorithm, Flow chart for Genetic programming. 03-15 2. Encoding Binary Encoding, Value Encoding, Permutation Encoding, and Tree Encoding. 16-21 3. Operators of Genetic Algorithm Reproduction or selection : Roulette wheel selection, Boltzmann selection; fitness function; Crossover: one-Point crossover, two-Point crossover, uniform crossover, arithmetic, heuristic; Mutation : flip bit, boundary, non-uniform, uniform, Gaussian. 22-35 4. Basic Genetic Algorithm Solved examples : maximize function f(x) = x 2 and two bar pendulum. 36-41 5. References 42 02 RC Chakraborty, www.myreaders.info Fundamentals of Genetic Algorithms What are GAs ? • Genetic Algorithms (GAs) are adaptive heuristic search algorithm based on the evolutionary ideas of natural selection and genetics. • Genetic algorithms (GAs) are a part of Evolutionary computing, a rapidly growing area of artificial intelligence. GAs are inspired by Darwin's theory about evolution - "survival of the fittest". • GAs represent an intelligent exploitation of a random search used to solve optimization problems. • GAs, although randomized, exploit historical information to direct the search into the region of better performance within the search space. • In nature, competition among individuals for scanty resources results in the fittest individuals dominating over the weaker ones. 03 RC Chakraborty, www.myreaders.info GA - Introduction 1. Introduction to Genetic Algorithms Solving problems mean looking for solutions, which is best among others. Finding the solution to a problem is often thought : − In computer science and AI, as a process of search through the space of possible solutions. The set of possible solutions defines the search space (also called state space) for a given problem. Solutions or partial solutions are viewed as points in the search space. − In engineering and mathematics, as a process of optimization. The problems are first formulated as mathematical models expressed in terms of functions and then to find a solution, discover the parameters that optimize the model or the function components...
Website: www.myreaders.info | Filesize: -
No of Page(s): 42
Download Fundamentals of Genetic Algorithms Artificial ... - Myreaders.info.pdf
A Parallel Particle Swarm Optimization Algorithm
6th World Congresses of Structural and Multidisciplinary Optimization Rio de Janeiro, 30 May - 03 June 2005, Brazil A Parallel Particle Swarm Optimization Algorithm Accelerated by Asynchronous Evaluations Gerhard Venter (gventer@vrand.com), Jaroslaw Sobieszczanski-Sobieski (j.sobieski@larc.nasa.gov) Vanderplaats Research and Development, Colorado Springs, USA NASA Langley Research Center, Hampton, USA 1. Abstract A parallel Particle Swarm Optimization (PSO) algorithm is presented. Particle swarm optimization is a fairly recent addition to the family of non-gradient based, probabilistic search algorithms that is based on a
simplified social model and is closely tied to swarming theory. Although PSO algorithms present several attractive properties to the designer, they are plagued by high computational cost as measured by elapsed time. One approach to reduce the elapsed time is to make use of coarse-grained parallelization to evaluate the design points. Previous parallel PSO algorithms were mostly implemented in a synchronous manner, where all design points within a design iteration are evaluated before the next iteration is started. This approach leads to poor parallel speedup in cases where a heterogeneous parallel environment is used and/or where the analysis time depends on the design point being analyzed. This paper introduces an asynchronous parallel PSO algorithm that greatly improves the parallel efficiency. The asynchronous algorithm is benchmarked on a cluster assembled of Apple Macintosh G5 desktop computers, using the multi-disciplinary optimization of a typical transport aircraft wing as an example. 2. Keywords: Particle Swarm Optimization, PSO, asynchronous parallel computing 3. Introduction Particle Swarm Optimization (PSO) is a fairly recent, but rapidly growing, addition to an expanding collection of non-gradient based, probabilistic search algorithms. Some widely used algorithms that fall into this category are genetic algorithms [1] that model Darwin’s principle of survival of the fittest and simulated annealing algorithms [2] that model the equilibrium of large numbers of atoms during an annealing process. This class of optimization algorithms provides the designer with several attractive characteristics. For example, these algorithms are generally easy to implement, can efficiently make use of large numbers of parallel processors, do not require continuity in response functions and are better suited for finding global or near global solutions. Although these non-gradient based algorithms provide the designer with several advantages, they should be applied with care. Due to their high computational cost, these algorithms should only be used when a gradient-based algorithm is not a viable alternative, such as integer/discrete and discontinuous problems. Many non-gradient based search algorithms are based on some natural phenomena, and PSO is no exception. Particle swarm optimization is based on a simplified social model that is closely tied to swarming theory and was first introduced by Kennedy and Eberhart [3, 4]. A physical analogy might be a school of fish that is adapting to its environment. In this analogy, each fish adapts to its environment by making use of its own memory as well as knowledge gained by the school as a whole. Although...
Website: bioserver.cpgei.ct.utfpr.edu.br | Filesize: -
No of Page(s): 10
Download A Parallel Particle Swarm Optimization Algorithm ... - Bioserver.pdf
simplified social model and is closely tied to swarming theory. Although PSO algorithms present several attractive properties to the designer, they are plagued by high computational cost as measured by elapsed time. One approach to reduce the elapsed time is to make use of coarse-grained parallelization to evaluate the design points. Previous parallel PSO algorithms were mostly implemented in a synchronous manner, where all design points within a design iteration are evaluated before the next iteration is started. This approach leads to poor parallel speedup in cases where a heterogeneous parallel environment is used and/or where the analysis time depends on the design point being analyzed. This paper introduces an asynchronous parallel PSO algorithm that greatly improves the parallel efficiency. The asynchronous algorithm is benchmarked on a cluster assembled of Apple Macintosh G5 desktop computers, using the multi-disciplinary optimization of a typical transport aircraft wing as an example. 2. Keywords: Particle Swarm Optimization, PSO, asynchronous parallel computing 3. Introduction Particle Swarm Optimization (PSO) is a fairly recent, but rapidly growing, addition to an expanding collection of non-gradient based, probabilistic search algorithms. Some widely used algorithms that fall into this category are genetic algorithms [1] that model Darwin’s principle of survival of the fittest and simulated annealing algorithms [2] that model the equilibrium of large numbers of atoms during an annealing process. This class of optimization algorithms provides the designer with several attractive characteristics. For example, these algorithms are generally easy to implement, can efficiently make use of large numbers of parallel processors, do not require continuity in response functions and are better suited for finding global or near global solutions. Although these non-gradient based algorithms provide the designer with several advantages, they should be applied with care. Due to their high computational cost, these algorithms should only be used when a gradient-based algorithm is not a viable alternative, such as integer/discrete and discontinuous problems. Many non-gradient based search algorithms are based on some natural phenomena, and PSO is no exception. Particle swarm optimization is based on a simplified social model that is closely tied to swarming theory and was first introduced by Kennedy and Eberhart [3, 4]. A physical analogy might be a school of fish that is adapting to its environment. In this analogy, each fish adapts to its environment by making use of its own memory as well as knowledge gained by the school as a whole. Although...
Website: bioserver.cpgei.ct.utfpr.edu.br | Filesize: -
No of Page(s): 10
Download A Parallel Particle Swarm Optimization Algorithm ... - Bioserver.pdf
Application of a particle swarm optimization algorithm
Application of a particle swarm optimization algorithm for determining optimum well location and type Jerome Onwunalu Louis J. Durlofsky Smart Fields Meeting April 8, 2009 Outline Introduction Optimization of well placement Algorithms for well placement optimization Genetic algorithm (GA) Particle swarm optimization (PSO) Examples Conclusions April 8, 2009 Smart Fields 2 Introduction Oil field development Optimize placement of wells Optimize well type Incorporate field constraints Account for geological uncertainty Expensive simulation runs April 8, 2009 Smart Fields 3 Introduction Oil
field development Optimize placement of wells Optimize well type Incorporate field constraints Account for geological uncertainty Expensive simulation runs April 8, 2009 Smart Fields 4 Well placement optimization problem Features Multidimensional Multimodal - many local optima Constrained Mixed variables Lack of analytical derivatives Discontinuous objective functions April 8, 2009 Smart Fields 5 Well placement optimization problem Features Multidimensional Multimodal - many local optima Constrained Mixed variables Lack of analytical derivatives Discontinuous objective functions April 8, 2009 Smart Fields 6 Well placement optimization algorithms Adjoint-based algorithms Stochastic approximation (SA) algorithms Simultaneous perturbation SA algorithm (SPSA) Finite difference SA algorithm (FDSA) Genetic algorithm (GA) Particle swarm optimization (PSO) algorithm April 8, 2009 Smart Fields 7 Well placement optimization algorithms Adjoint-based algorithms Stochastic approximation (SA) algorithms Simultaneous perturbation SA algorithm (SPSA) Finite difference SA algorithm (FDSA) Genetic algorithm (GA) Particle swarm optimization (PSO) algorithm April 8, 2009 Smart Fields 8 Genetic algorithm (GA) Overview Based on Darwinian evolutionary theory Population-based Members of the population are called individuals Determine the fitness (quality) of each individual using an objective function Rank population according to fitness Produce new population using best individuals GA operators Selection, Crossover, Mutation April 8, 2009 Smart Fields 9 GA flowchart April 8, 2009 Smart Fields 10 Particle swarm optimization (PSO) algorithm Overview Developed by Kennedy and Eberhardt (1995) Based on the social interaction exhibited by animals Particle refers to a potential solution Collection of particles is called swarm Population-based Update particles using a cognitive and social model Improve performance using different particle neighborhood topologies April 8, 2009 Smart Fields 11 Examples of PSO neighborhood topologies 1 2 3 4 567 8 (a) Star 1 2 3 4 567 8 (b) Ring 1 2 3 4 5 6 7 8 (c) Cluster April 8, 2009 Smart Fields 12 PSO variants and update equation PSO variants Global best PSO (gBest) - one neighborhood Local best PSO (lBest)- several neighborhoods Solution update equation xi(k + 1) = xi(k) + vi(k + 1) vi(k + 1) is the velocity of particle i April 8, 2009 Smart Fields 13 PSO variants and update equation PSO variants Global best PSO (gBest) - one neighborhood Local best PSO (lBest)- several neighborhoods Solution update equation xi(k + 1) = xi(k) + vi(k + 1) vi(k + 1) is the velocity of particle i April 8, 2009 Smart Fields 14 PSO variants and update equation PSO variants Global best PSO...
Website: smartfields.stanford.edu | Filesize: -
No of Page(s): 53
Download Application of a particle swarm optimization algorithm for ....pdf
field development Optimize placement of wells Optimize well type Incorporate field constraints Account for geological uncertainty Expensive simulation runs April 8, 2009 Smart Fields 4 Well placement optimization problem Features Multidimensional Multimodal - many local optima Constrained Mixed variables Lack of analytical derivatives Discontinuous objective functions April 8, 2009 Smart Fields 5 Well placement optimization problem Features Multidimensional Multimodal - many local optima Constrained Mixed variables Lack of analytical derivatives Discontinuous objective functions April 8, 2009 Smart Fields 6 Well placement optimization algorithms Adjoint-based algorithms Stochastic approximation (SA) algorithms Simultaneous perturbation SA algorithm (SPSA) Finite difference SA algorithm (FDSA) Genetic algorithm (GA) Particle swarm optimization (PSO) algorithm April 8, 2009 Smart Fields 7 Well placement optimization algorithms Adjoint-based algorithms Stochastic approximation (SA) algorithms Simultaneous perturbation SA algorithm (SPSA) Finite difference SA algorithm (FDSA) Genetic algorithm (GA) Particle swarm optimization (PSO) algorithm April 8, 2009 Smart Fields 8 Genetic algorithm (GA) Overview Based on Darwinian evolutionary theory Population-based Members of the population are called individuals Determine the fitness (quality) of each individual using an objective function Rank population according to fitness Produce new population using best individuals GA operators Selection, Crossover, Mutation April 8, 2009 Smart Fields 9 GA flowchart April 8, 2009 Smart Fields 10 Particle swarm optimization (PSO) algorithm Overview Developed by Kennedy and Eberhardt (1995) Based on the social interaction exhibited by animals Particle refers to a potential solution Collection of particles is called swarm Population-based Update particles using a cognitive and social model Improve performance using different particle neighborhood topologies April 8, 2009 Smart Fields 11 Examples of PSO neighborhood topologies 1 2 3 4 567 8 (a) Star 1 2 3 4 567 8 (b) Ring 1 2 3 4 5 6 7 8 (c) Cluster April 8, 2009 Smart Fields 12 PSO variants and update equation PSO variants Global best PSO (gBest) - one neighborhood Local best PSO (lBest)- several neighborhoods Solution update equation xi(k + 1) = xi(k) + vi(k + 1) vi(k + 1) is the velocity of particle i April 8, 2009 Smart Fields 13 PSO variants and update equation PSO variants Global best PSO (gBest) - one neighborhood Local best PSO (lBest)- several neighborhoods Solution update equation xi(k + 1) = xi(k) + vi(k + 1) vi(k + 1) is the velocity of particle i April 8, 2009 Smart Fields 14 PSO variants and update equation PSO variants Global best PSO...
Website: smartfields.stanford.edu | Filesize: -
No of Page(s): 53
Download Application of a particle swarm optimization algorithm for ....pdf
A Gender-Based Genetic Algorithm
A problem that is inherent to the development and efficient use of solvers is that of tuning parameters. The CP community has a long history of ad- dressing this task automatically. We propose a robust, inherently parallel genetic algorithm for the problem of configuring solvers automatically. In order to cope with the high costs of evaluating the fitness of individuals, we introduce a gender separation whereby we apply different selection pressure on both genders. Exper-
imental results on a selection of SAT solvers show significant performance and robustness gains over the current state-of-the-art in automatic algorithm configu- ration. 1 Introduction We consider the problem of automatic solver configuration. Practically all solvers have parameters that are partly fixed by the programmer and partly set by the user. In recent years, systems have been devised which automate the task of tuning parameters for a given set of training instances that are assumed to represent typical instances for the target algorithm. There are several motivations for such an automation, the first being that it is of course time consuming to tune parameters and it may lead to better results when leaving the configuration of solvers to a computer rather than doing it by hand. Moreover, it is conceivable that the existence of an effective tuning environment will cause algorithm developers to parameterize more aspects of their algorithms and thus leave more freedom for algorithmic solutions that are automatically tailored to the problems of individual users. In particular, many of the SAT solvers that are available today have parameters which cannot be set through the command line. These parameters have been fixed to values that the developers have found beneficial without knowledge about the particular instances a user may want to use the solver for. Automatic parameter tuning allows solvers to adapt to the final environment in which they need to perform. After being shipped, rather than relying on default parameters, an algorithm can be star This work was partly supported by the projects TIN2007-68005-C04-04 and TIN2006-15662- C02-02 funded by the MEC, and by the the National Science Foundation through the Ca- reer: Cornflower Project (award number 0644113). I.P. Gent (Ed.): CP 2009, LNCS 5732, pp. 142–157, 2009. c©Springer-Verlag Berlin Heidelberg 2009 A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms 143 tuned automatically for the common tasks it is actually used for, and without requiring the user to learn about the algorithm parameters. For this very reason, Cplex 11 now comes with an automatic performance tuning tool. Another argument for automatic solver configuration regards our own science: when we re-implement algorithms to conduct experimental comparisons with competing ap- proaches, it is not unreasonable to assume that scientists spend much more time tuning their own algorithm than the algorithms of their competitors. A fair comparison could be achieved if all algorithms were tuned by an independent system. That...
Website: cs.brown.edu | Filesize: -
No of Page(s): 16
Download A Gender-Based Genetic Algorithm for the ... - Brown University.pdf
imental results on a selection of SAT solvers show significant performance and robustness gains over the current state-of-the-art in automatic algorithm configu- ration. 1 Introduction We consider the problem of automatic solver configuration. Practically all solvers have parameters that are partly fixed by the programmer and partly set by the user. In recent years, systems have been devised which automate the task of tuning parameters for a given set of training instances that are assumed to represent typical instances for the target algorithm. There are several motivations for such an automation, the first being that it is of course time consuming to tune parameters and it may lead to better results when leaving the configuration of solvers to a computer rather than doing it by hand. Moreover, it is conceivable that the existence of an effective tuning environment will cause algorithm developers to parameterize more aspects of their algorithms and thus leave more freedom for algorithmic solutions that are automatically tailored to the problems of individual users. In particular, many of the SAT solvers that are available today have parameters which cannot be set through the command line. These parameters have been fixed to values that the developers have found beneficial without knowledge about the particular instances a user may want to use the solver for. Automatic parameter tuning allows solvers to adapt to the final environment in which they need to perform. After being shipped, rather than relying on default parameters, an algorithm can be star This work was partly supported by the projects TIN2007-68005-C04-04 and TIN2006-15662- C02-02 funded by the MEC, and by the the National Science Foundation through the Ca- reer: Cornflower Project (award number 0644113). I.P. Gent (Ed.): CP 2009, LNCS 5732, pp. 142–157, 2009. c©Springer-Verlag Berlin Heidelberg 2009 A Gender-Based Genetic Algorithm for the Automatic Configuration of Algorithms 143 tuned automatically for the common tasks it is actually used for, and without requiring the user to learn about the algorithm parameters. For this very reason, Cplex 11 now comes with an automatic performance tuning tool. Another argument for automatic solver configuration regards our own science: when we re-implement algorithms to conduct experimental comparisons with competing ap- proaches, it is not unreasonable to assume that scientists spend much more time tuning their own algorithm than the algorithms of their competitors. A fair comparison could be achieved if all algorithms were tuned by an independent system. That...
Website: cs.brown.edu | Filesize: -
No of Page(s): 16
Download A Gender-Based Genetic Algorithm for the ... - Brown University.pdf
Friday, September 28, 2012
Scalable Force Directed Graph Layout Algorithms Using Fast Multipole
Scalable Force Directed Graph Layout Algorithms Using Fast Multipole Methods Enas Yunis, Rio Yokota and Aron Ahmadia King Abdullah University of Science and Technology 4700 KAUST, Thuwal, KSA 23955-6900 fenas.yunis, rio.yokota, aron.ahmadiag @kaust.edu.sa Abstract—We present an extension to ExaFMM, a Fast Multipole Method library, as a generalized approach for fast and scalable execution of the Force-Directed Graph Layout algorithm. The Force-Directed Graph Layout algorithm is a physics-based approach to graph layout that treats the vertices V as repelling charged particles
with the edges E connecting them acting as springs. Traditionally, the amount of work re- quired in applying the Force-Directed Graph Layout algorithm is O(jVj2 +jEj) using direct calculations and O(jVjlogjVj+ jEj) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(jVj + jEj) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still re- quires a scalable algorithm and implementation. We have been able to leverage the scalability and architectural adaptability of the ExaFMM library to create a Force-Directed Graph Layout implementation that runs efficiently on distributed multicore and multi-GPU architectures. Keywords-Force directed graph layout; Fast multipole meth- ods; Multi-GPUs I. INTRODUCTION Force-Directed Graph Layout (FDGL) is a popular al- gorithm for automatically generating aesthetically pleasing 2D and 3D visualizations of large sparse graphs [1], [2]. FDGL is a physics-based approach to graph layout that treats the vertices as repelling charged particles and the edges connecting them as springs. Given a graph G = (V;E) consisting of a set of vertices V and a set of undirected edges E, a graph layout algorithm associates a position xd for each vertex v in V . FDGL works by assigning an initial random position x0 to each vertex and interactive forces between each vertex (usually an electromagnetic-style repulsion between each vertex modeled after Coulomb’s Law and attractive linear springs among edges modeled after Hooke’s Law), then using either global optimization heuristics to find a configuration of minimal potential energy, where the system’s potential energy P is computed by summing the repulsive vertex-vertex potential interaction energies Pv and the edge potential energies Pe over all vertices. A common heuristic for minimizing potential energy is simulated annealing, [1], [3] where a “warm” system with vertices allowed to freely move is gradually “cooled” allowing the algorithm to occasionally escape local minima in optimizing P. There are several commonly used stopping criterion; [3] bases their approach on total system energy, while [1] relies on a direct temperature cooling technique. Additionally, there are a large variety of force models for interactions, some can be easily connected to existing physical models, while others rely on purely mathematical constructions. Calculating the repulsive interactions na¨ıvely using direct integration requires O(jVj2) computations [1], [2]. Addi- tionally, O(jEj) computations per iteration are needed for spring calculations. Given...
Website: www.bu.edu | Filesize: -
No of Page(s): 7
Download Scalable Force Directed Graph Layout Algorithms Using Fast Multipole.pdf
with the edges E connecting them acting as springs. Traditionally, the amount of work re- quired in applying the Force-Directed Graph Layout algorithm is O(jVj2 +jEj) using direct calculations and O(jVjlogjVj+ jEj) using truncation, filtering, and/or multi-level techniques. Correct application of the Fast Multipole Method allows us to maintain a lower complexity of O(jVj + jEj) while regaining most of the precision lost in other techniques. Solving layout problems for truly large graphs with millions of vertices still re- quires a scalable algorithm and implementation. We have been able to leverage the scalability and architectural adaptability of the ExaFMM library to create a Force-Directed Graph Layout implementation that runs efficiently on distributed multicore and multi-GPU architectures. Keywords-Force directed graph layout; Fast multipole meth- ods; Multi-GPUs I. INTRODUCTION Force-Directed Graph Layout (FDGL) is a popular al- gorithm for automatically generating aesthetically pleasing 2D and 3D visualizations of large sparse graphs [1], [2]. FDGL is a physics-based approach to graph layout that treats the vertices as repelling charged particles and the edges connecting them as springs. Given a graph G = (V;E) consisting of a set of vertices V and a set of undirected edges E, a graph layout algorithm associates a position xd for each vertex v in V . FDGL works by assigning an initial random position x0 to each vertex and interactive forces between each vertex (usually an electromagnetic-style repulsion between each vertex modeled after Coulomb’s Law and attractive linear springs among edges modeled after Hooke’s Law), then using either global optimization heuristics to find a configuration of minimal potential energy, where the system’s potential energy P is computed by summing the repulsive vertex-vertex potential interaction energies Pv and the edge potential energies Pe over all vertices. A common heuristic for minimizing potential energy is simulated annealing, [1], [3] where a “warm” system with vertices allowed to freely move is gradually “cooled” allowing the algorithm to occasionally escape local minima in optimizing P. There are several commonly used stopping criterion; [3] bases their approach on total system energy, while [1] relies on a direct temperature cooling technique. Additionally, there are a large variety of force models for interactions, some can be easily connected to existing physical models, while others rely on purely mathematical constructions. Calculating the repulsive interactions na¨ıvely using direct integration requires O(jVj2) computations [1], [2]. Addi- tionally, O(jEj) computations per iteration are needed for spring calculations. Given...
Website: www.bu.edu | Filesize: -
No of Page(s): 7
Download Scalable Force Directed Graph Layout Algorithms Using Fast Multipole.pdf
A Potential-Field-Based Multilevel Algorithm
I would like to thank everyone who supported me in writing this thesis. In particular, many thanks are addressed to my supervisor Prof. Dr. Michael J¨unger for giving me the possibility to research in the field of force-directed graph drawing and for the constructive and helpful discussions in the internal seminars. I am very grateful to Dr. Sebastian Leipert for bringing me to the research field of automatic graph drawing and to HD Dr. Bert Randerath and Claudia Schlesiger for their proof-reading.
Many thanks go to Thomas Lange, Constantin Hellweg, Holger Flier, and Annette Menze for supporting me in all technical questions. Without their assistance and profes- sional work, this dissertation would probably still be in progress. I thank Michael Belling and Ursula Neugebauer for helping me in the acquisition of literature and all administrative processes. A big thank goes also to Dr. Christoph Buchheim, Matthias Elf, Dr. Frauke Liers, Merijam Percan, and all previous mentioned colleagues for their “open doors” in the last years in Cologne. Furthermore, I would like to thank Yehuda Koren, Daniel Tunkelang, and Roman Yusufov for making me available the implementations of their algorithms. Finally, I am very grateful to my girlfriend Claudia Schlesiger and my parents Gerda Hachul and Paul Hachul for supporting me in all aspects of my life. Abstract The aim of automatic graph drawing is to compute a well-readable layout of a given graph G = (V,E). One very popular class of algorithms for drawing general graphs are force- directed methods. These methods generate drawings of G in the plane so that each edge is represented by a straight line connecting its two adjacent nodes. The computation of the drawings is based on associating G with a physical model. Then, the algorithms iteratively try to find a placement of the nodes so that the total energy of the physical system is minimal. Several force-directed methods can visualize large graphs containing many thousands of vertices in reasonable time. However, only some of these methods guarantee a sub-quadratic running time in special cases or under certain assumptions, but not in general. The others are not sub-quadratic at all. We develop a new force-directed algorithm that is based on a combination of an effi- cient multilevel strategy and a method for approximating the repulsive forces in the system by rapidly evaluating potential fields. The worst-case running time of the new method is O(|V|log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing up to 100000 nodes in less than five minutes. Fur- thermore, it clearly visualizes even the structures of those graphs that turned...
Website: kups.ub.uni-koeln.de | Filesize: -
No of Page(s): 198
Download A Potential-Field-Based Multilevel Algorithm for ... - Universität zu Köln.pdf
Many thanks go to Thomas Lange, Constantin Hellweg, Holger Flier, and Annette Menze for supporting me in all technical questions. Without their assistance and profes- sional work, this dissertation would probably still be in progress. I thank Michael Belling and Ursula Neugebauer for helping me in the acquisition of literature and all administrative processes. A big thank goes also to Dr. Christoph Buchheim, Matthias Elf, Dr. Frauke Liers, Merijam Percan, and all previous mentioned colleagues for their “open doors” in the last years in Cologne. Furthermore, I would like to thank Yehuda Koren, Daniel Tunkelang, and Roman Yusufov for making me available the implementations of their algorithms. Finally, I am very grateful to my girlfriend Claudia Schlesiger and my parents Gerda Hachul and Paul Hachul for supporting me in all aspects of my life. Abstract The aim of automatic graph drawing is to compute a well-readable layout of a given graph G = (V,E). One very popular class of algorithms for drawing general graphs are force- directed methods. These methods generate drawings of G in the plane so that each edge is represented by a straight line connecting its two adjacent nodes. The computation of the drawings is based on associating G with a physical model. Then, the algorithms iteratively try to find a placement of the nodes so that the total energy of the physical system is minimal. Several force-directed methods can visualize large graphs containing many thousands of vertices in reasonable time. However, only some of these methods guarantee a sub-quadratic running time in special cases or under certain assumptions, but not in general. The others are not sub-quadratic at all. We develop a new force-directed algorithm that is based on a combination of an effi- cient multilevel strategy and a method for approximating the repulsive forces in the system by rapidly evaluating potential fields. The worst-case running time of the new method is O(|V|log|V|+|E|) with linear memory requirements. In practice, the algorithm generates nice drawings of graphs containing up to 100000 nodes in less than five minutes. Fur- thermore, it clearly visualizes even the structures of those graphs that turned...
Website: kups.ub.uni-koeln.de | Filesize: -
No of Page(s): 198
Download A Potential-Field-Based Multilevel Algorithm for ... - Universität zu Köln.pdf
An Introduction to Genetic Algorithms - Boente
An Introduction to Genetic Algorithms Mitchell Melanie A Bradford Book The MIT Press Cambridge, Massachusetts • London, England Fifth printing, 1999 First MIT Press paperback edition, 1998 Copyright © 1996 Massachusetts Institute of Technology All rights reserved. No part of this publication may be reproduced in any form by any electronic or mechanical means (including photocopying, recording, or information storage and retrieval) without permission in writing from the publisher. Set in Palatino by Windfall Software using ZzT E X. Library
of Congress Cataloging−in−Publication Data Mitchell, Melanie. An introduction to genetic algorithms / Melanie Mitchell. p. cm. "A Bradford book." Includes bibliographical references and index. ISBN 0−262−13316−4 (HB), 0−262−63185−7 (PB) 1. Genetics—Computer simulation.2. Genetics—Mathematical models.I. Title. QH441.2.M55 1996 575.1'01'13—dc20 95−24489 CIP 1 Table of Contents An Introduction to Genetic Algorithms............................................................................................................1 Mitchell Melanie......................................................................................................................................1 Chapter 1: Genetic Algorithms: An Overview.................................................................................................2 Overview..................................................................................................................................................2 1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION.....................................................2 1.2 THE APPEAL OF EVOLUTION.....................................................................................................4 1.3 BIOLOGICAL TERMINOLOGY.....................................................................................................5 1.4 SEARCH SPACES AND FITNESS LANDSCAPES.......................................................................6 1.5 ELEMENTS OF GENETIC ALGORITHMS...................................................................................7 Examples of Fitness Functions...................................................................................................7 GA Operators..............................................................................................................................8 1.6 A SIMPLE GENETIC ALGORITHM..............................................................................................8 1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS..................................10 1.9 TWO BRIEF EXAMPLES..............................................................................................................12 Using GAs to Evolve Strategies for the Prisoner's Dilemma...................................................13 Hosts and Parasites: Using GAs to Evolve Sorting Networks..................................................16 1.10 HOW DO GENETIC ALGORITHMS WORK?...........................................................................21 THOUGHT EXERCISES......................................................................................................................23 COMPUTER EXERCISES...................................................................................................................24 Chapter 2: Genetic Algorithms in Problem Solving......................................................................................27 Overview................................................................................................................................................27 2.1 EVOLVING COMPUTER PROGRAMS.......................................................................................27 Evolving Lisp Programs...........................................................................................................27 Evolving Cellular Automata.....................................................................................................34 2.2 DATA ANALYSIS AND PREDICTION.......................................................................................42 Predicting Dynamical Systems.................................................................................................42 Predicting Protein Structure......................................................................................................47 2.3 EVOLVING NEURAL NETWORKS............................................................................................49 Evolving Weights in a Fixed Network.....................................................................................50 Evolving Network Architectures..............................................................................................53 Direct Encoding........................................................................................................................54 Grammatical Encoding.............................................................................................................55 Evolving a Learning Rule.........................................................................................................58 THOUGHT EXERCISES......................................................................................................................60 COMPUTER EXERCISES...................................................................................................................62 Chapter 3: Genetic Algorithms in Scientific Models.....................................................................................65 Overview................................................................................................................................................65 3.1 MODELING INTERACTIONS BETWEEN LEARNING AND EVOLUTION...........................66 The Baldwin Effect...................................................................................................................66 A Simple Model of the Baldwin Effect....................................................................................68 Evolutionary Reinforcement Learning.....................................................................................72 3.2 MODELING SEXUAL SELECTION.............................................................................................75 Simulation and Elaboration of a Mathematical Model for Sexual Selection...........................76 3.3 MODELING ECOSYSTEMS.........................................................................................................78 3.4 MEASURING EVOLUTIONARY ACTIVITY.............................................................................81 Thought Exercises..................................................................................................................................84 Computer Exercises...............................................................................................................................85 Table of Contents Chapter 4: Theoretical Foundations of Genetic Algorithms........................................................................87 Overview................................................................................................................................................87 4.1 SCHEMAS AND THE TWO−ARMED BANDIT PROBLEM.....................................................87 The Two−Armed Bandit Problem............................................................................................88 Sketch of a Solution..................................................................................................................89 Interpretation of the Solution....................................................................................................91 Implications for GA Performance.............................................................................................92 Deceiving a Genetic Algorithm................................................................................................93 Limitations of "Static" Schema Analysis..................................................................................93 4.2 ROYAL ROADS.............................................................................................................................94 Royal Road Functions...............................................................................................................94 Experimental Results................................................................................................................95 Steepest−ascent hill climbing (SAHC).....................................................................................96 Next−ascent hill climbing (NAHC)..........................................................................................96 Random−mutation hill climbing (RMHC)...............................................................................96 Analysis of Random−Mutation Hill Climbing.........................................................................97 Hitchhiking in the Genetic Algorithm......................................................................................98 An Idealized Genetic Algorithm...............................................................................................99 4.3 EXACT MATHEMATICAL MODELS OF SIMPLE GENETIC ALGORITHMS.....................103 Formalization of GAs.............................................................................................................103 Results of the Formalization...................................................................................................108 A Finite−Population Model....................................................................................................108 4.4 STATISTICAL−MECHANICS APPROACHES.........................................................................112 THOUGHT EXERCISES....................................................................................................................114 COMPUTER EXERCISES.................................................................................................................116 5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?........................................................116 5.2 ENCODING A PROBLEM FOR A GENETIC ALGORITHM...................................................117 Binary Encodings....................................................................................................................117 Many−Character and Real−Valued Encodings......................................................................118 Tree Encodings.......................................................................................................................118 5.3 ADAPTING THE ENCODING....................................................................................................118 Inversion.................................................................................................................................119 Evolving Crossover "Hot Spots"............................................................................................120 Messy Gas...............................................................................................................................121 5.4 SELECTION METHODS.............................................................................................................124 Fitness−Proportionate Selection with "Roulette Wheel" and "Stochastic Universal" Sampling................................................................................................................................124 Sigma Scaling.........................................................................................................................125 Elitism.....................................................................................................................................126 Boltzmann Selection...............................................................................................................126 Rank Selection........................................................................................................................127 Tournament Selection.............................................................................................................127 Steady−State...
Website: www.boente.eti.br | Filesize: -
No of Page(s): 162
Download An Introduction to Genetic Algorithms - Boente.pdf
of Congress Cataloging−in−Publication Data Mitchell, Melanie. An introduction to genetic algorithms / Melanie Mitchell. p. cm. "A Bradford book." Includes bibliographical references and index. ISBN 0−262−13316−4 (HB), 0−262−63185−7 (PB) 1. Genetics—Computer simulation.2. Genetics—Mathematical models.I. Title. QH441.2.M55 1996 575.1'01'13—dc20 95−24489 CIP 1 Table of Contents An Introduction to Genetic Algorithms............................................................................................................1 Mitchell Melanie......................................................................................................................................1 Chapter 1: Genetic Algorithms: An Overview.................................................................................................2 Overview..................................................................................................................................................2 1.1 A BRIEF HISTORY OF EVOLUTIONARY COMPUTATION.....................................................2 1.2 THE APPEAL OF EVOLUTION.....................................................................................................4 1.3 BIOLOGICAL TERMINOLOGY.....................................................................................................5 1.4 SEARCH SPACES AND FITNESS LANDSCAPES.......................................................................6 1.5 ELEMENTS OF GENETIC ALGORITHMS...................................................................................7 Examples of Fitness Functions...................................................................................................7 GA Operators..............................................................................................................................8 1.6 A SIMPLE GENETIC ALGORITHM..............................................................................................8 1.7 GENETIC ALGORITHMS AND TRADITIONAL SEARCH METHODS..................................10 1.9 TWO BRIEF EXAMPLES..............................................................................................................12 Using GAs to Evolve Strategies for the Prisoner's Dilemma...................................................13 Hosts and Parasites: Using GAs to Evolve Sorting Networks..................................................16 1.10 HOW DO GENETIC ALGORITHMS WORK?...........................................................................21 THOUGHT EXERCISES......................................................................................................................23 COMPUTER EXERCISES...................................................................................................................24 Chapter 2: Genetic Algorithms in Problem Solving......................................................................................27 Overview................................................................................................................................................27 2.1 EVOLVING COMPUTER PROGRAMS.......................................................................................27 Evolving Lisp Programs...........................................................................................................27 Evolving Cellular Automata.....................................................................................................34 2.2 DATA ANALYSIS AND PREDICTION.......................................................................................42 Predicting Dynamical Systems.................................................................................................42 Predicting Protein Structure......................................................................................................47 2.3 EVOLVING NEURAL NETWORKS............................................................................................49 Evolving Weights in a Fixed Network.....................................................................................50 Evolving Network Architectures..............................................................................................53 Direct Encoding........................................................................................................................54 Grammatical Encoding.............................................................................................................55 Evolving a Learning Rule.........................................................................................................58 THOUGHT EXERCISES......................................................................................................................60 COMPUTER EXERCISES...................................................................................................................62 Chapter 3: Genetic Algorithms in Scientific Models.....................................................................................65 Overview................................................................................................................................................65 3.1 MODELING INTERACTIONS BETWEEN LEARNING AND EVOLUTION...........................66 The Baldwin Effect...................................................................................................................66 A Simple Model of the Baldwin Effect....................................................................................68 Evolutionary Reinforcement Learning.....................................................................................72 3.2 MODELING SEXUAL SELECTION.............................................................................................75 Simulation and Elaboration of a Mathematical Model for Sexual Selection...........................76 3.3 MODELING ECOSYSTEMS.........................................................................................................78 3.4 MEASURING EVOLUTIONARY ACTIVITY.............................................................................81 Thought Exercises..................................................................................................................................84 Computer Exercises...............................................................................................................................85 Table of Contents Chapter 4: Theoretical Foundations of Genetic Algorithms........................................................................87 Overview................................................................................................................................................87 4.1 SCHEMAS AND THE TWO−ARMED BANDIT PROBLEM.....................................................87 The Two−Armed Bandit Problem............................................................................................88 Sketch of a Solution..................................................................................................................89 Interpretation of the Solution....................................................................................................91 Implications for GA Performance.............................................................................................92 Deceiving a Genetic Algorithm................................................................................................93 Limitations of "Static" Schema Analysis..................................................................................93 4.2 ROYAL ROADS.............................................................................................................................94 Royal Road Functions...............................................................................................................94 Experimental Results................................................................................................................95 Steepest−ascent hill climbing (SAHC).....................................................................................96 Next−ascent hill climbing (NAHC)..........................................................................................96 Random−mutation hill climbing (RMHC)...............................................................................96 Analysis of Random−Mutation Hill Climbing.........................................................................97 Hitchhiking in the Genetic Algorithm......................................................................................98 An Idealized Genetic Algorithm...............................................................................................99 4.3 EXACT MATHEMATICAL MODELS OF SIMPLE GENETIC ALGORITHMS.....................103 Formalization of GAs.............................................................................................................103 Results of the Formalization...................................................................................................108 A Finite−Population Model....................................................................................................108 4.4 STATISTICAL−MECHANICS APPROACHES.........................................................................112 THOUGHT EXERCISES....................................................................................................................114 COMPUTER EXERCISES.................................................................................................................116 5.1 WHEN SHOULD A GENETIC ALGORITHM BE USED?........................................................116 5.2 ENCODING A PROBLEM FOR A GENETIC ALGORITHM...................................................117 Binary Encodings....................................................................................................................117 Many−Character and Real−Valued Encodings......................................................................118 Tree Encodings.......................................................................................................................118 5.3 ADAPTING THE ENCODING....................................................................................................118 Inversion.................................................................................................................................119 Evolving Crossover "Hot Spots"............................................................................................120 Messy Gas...............................................................................................................................121 5.4 SELECTION METHODS.............................................................................................................124 Fitness−Proportionate Selection with "Roulette Wheel" and "Stochastic Universal" Sampling................................................................................................................................124 Sigma Scaling.........................................................................................................................125 Elitism.....................................................................................................................................126 Boltzmann Selection...............................................................................................................126 Rank Selection........................................................................................................................127 Tournament Selection.............................................................................................................127 Steady−State...
Website: www.boente.eti.br | Filesize: -
No of Page(s): 162
Download An Introduction to Genetic Algorithms - Boente.pdf
Semi-Supervised Clustering Using Genetic Algorithms
Semi-Supervised Clustering Using Genetic Algorithms Ayhan Demiriz Dept. of Decision Sciences and Engineering Systems Kristin P. Bennett∗ Dept. of Mathematical Sciences Mark J. Embrechts Dept. Decision Sciences and Engineering Systems Rensselaer Polytechnic Institute Troy, NY 12180 May 26, 1999 Abstract A semi-supervised clustering algorithm is proposed that combines the benefits of supervised and unsupervised learning methods. Data are seg- mented/clustered using an unsupervised learning technique that is biased toward producing segments or clusters as pure as possible in terms of
class distribution. These clusters can then be used to predict the class of future points. For example in database marketing, the technique can be used to identify and characterize segments of the customer population likely to respond to a promotion. One benefit of the approach is that it allows unlabeled data with no known class to be used to improve classi- fication accuracy. The objective function of an unsupervised technique, e.g. K-means clustering, is modified to minimize both the within cluster variance of the input attributes and a measure of cluster impurity based on the class labels. Minimizing the within cluster variance of the examples is a form of capacity control to prevent overfitting. For the the output labels, impurity measures from decision tree algorithms such as the Gini index can be used. A genetic algorithm optimizes the objective function to produce clusters. Non-empty clusters are labeled with the majority class. Experimental results show that using class information improves the generalization ability compared to unsupervised methods based only on the input attributes. The results also indicate that the method per- forms very well even when few training examples are available. Training using information from unlabeled data can improve classification accuracy on that data as well. ∗http://www.math.rpi.edu/ bennek 1 1 Introduction In this work, we examine an approach to solve classification problems that com- bines supervised and unsupervised learning techniques. In supervised learning, we assume we are given a set of labeled training points, and the task is to construct some function that will correctly predict the labels of future points. In unsupervised learning such as clustering, the task is to segment unlabeled training data into clusters that reflect some meaningful structure in the data. For the Semi-Supervised Learning Problem (SSLP) we assume that we are given both labeled and unlabeled points. The task is then to predict the labels of the unlabeled points using all the available labeled data, as well as unlabeled data. One would expect a better generalization abilityof the resulting classifier due to the better understanding of the input distribution resulting from using all the available data. The semi-supervised learning problem can be used to perform transductive inference [17]. In transduction, we are given a set of training data and a set of testing data, and the learning task is to predict the labels of the specific testing data only. Different testing data will produce different classifica-...
Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 20
Download Semi-Supervised Clustering Using Genetic Algorithms.pdf
class distribution. These clusters can then be used to predict the class of future points. For example in database marketing, the technique can be used to identify and characterize segments of the customer population likely to respond to a promotion. One benefit of the approach is that it allows unlabeled data with no known class to be used to improve classi- fication accuracy. The objective function of an unsupervised technique, e.g. K-means clustering, is modified to minimize both the within cluster variance of the input attributes and a measure of cluster impurity based on the class labels. Minimizing the within cluster variance of the examples is a form of capacity control to prevent overfitting. For the the output labels, impurity measures from decision tree algorithms such as the Gini index can be used. A genetic algorithm optimizes the objective function to produce clusters. Non-empty clusters are labeled with the majority class. Experimental results show that using class information improves the generalization ability compared to unsupervised methods based only on the input attributes. The results also indicate that the method per- forms very well even when few training examples are available. Training using information from unlabeled data can improve classification accuracy on that data as well. ∗http://www.math.rpi.edu/ bennek 1 1 Introduction In this work, we examine an approach to solve classification problems that com- bines supervised and unsupervised learning techniques. In supervised learning, we assume we are given a set of labeled training points, and the task is to construct some function that will correctly predict the labels of future points. In unsupervised learning such as clustering, the task is to segment unlabeled training data into clusters that reflect some meaningful structure in the data. For the Semi-Supervised Learning Problem (SSLP) we assume that we are given both labeled and unlabeled points. The task is then to predict the labels of the unlabeled points using all the available labeled data, as well as unlabeled data. One would expect a better generalization abilityof the resulting classifier due to the better understanding of the input distribution resulting from using all the available data. The semi-supervised learning problem can be used to perform transductive inference [17]. In transduction, we are given a set of training data and a set of testing data, and the learning task is to predict the labels of the specific testing data only. Different testing data will produce different classifica-...
Website: reference.kfupm.edu.sa | Filesize: -
No of Page(s): 20
Download Semi-Supervised Clustering Using Genetic Algorithms.pdf
The particle swarm optimization algorithm
The particle swarm optimization algorithm: convergence analysis and parameter selection Ioan Cristian Trelea INA P-G, UMR Génie et Microbiologie des Procédés Alimentaires, BP 01, 78850 Thiverval-Grignon, France Received 10 July 2002; received in revised form 12 September 2002 Communicated by S. Albers Abstract The particle swarm optimization algorithm is analyzed using standard results from the dynamic system theory. Graphical parameter selection guidelines are derived. The exploration–exploitation tradeoff is discussed and illustrated. Examples of
performance on benchmark functions superior to previously published results are given. 2002 Elsevier Science B.V. All rights reserved. Keywords: Particle swarm optimization; Stochastic optimization; Analysis of algorithms; Parallel algorithms 1. Introduction The particle swarm optimization (PSO) is a paral- lel evolutionary computation technique developed by Kennedy and Eberhart [4] based on the social behav- ior metaphor. A standard textbook on PSO, treating both the social and computational paradigms, is [5]. The PSO algorithm is initialized with a population of random candidate solutions, conceptualized as parti- cles. Each particle is assigned a randomized velocity and is iteratively moved through the problem space. It is attracted towards the location of the best fitness achieved so far by the particle itself and by the loca- tion of the best fitness achieved so far across the whole population (global version of the algorithm). The PSO algorithm includes some tuning parame- ters that greatly influence the algorithm performance, E-mail address: trelea@grignon.inra.fr (I.C. Trelea). often stated as the exploration–exploitation tradeoff: Exploration is the ability to test various regions in the problem space in order to locate a good optimum, hopefully the global one. Exploitation is the ability to concentrate the search around a promising candidate solution in order to locate the optimum precisely. De- spite recent research efforts, the selection of the al- gorithm parameters remains empirical to a large ex- tent. A complete theoretical analysis of the algorithm has been given by Clerc and Kennedy [2]. Based on this analysis, the authors derived a reasonable set of tuning parameters, as confirmed by [3]. The reference [2] contains a good deal of mathematical complex- ity, however, and deriving from it simple user-oriented guidelines for the parameter selection in a specific problem is not straightforward. The present work gives some additional insight into the PSO parameter selection topic. It is estab- lished that some of the parameters add no flexibil- ity to the algorithm and can be discarded without 0020-0190/02/$ – see front matter 2002 Elsevier Science B.V. All rights reserved. PII: S0020-0190(02)00447-7 318 I.C. Trelea / Information Processing Letters 85 (2003) 317–325 loss of generality. Results from the dynamic system theory are used for a relatively simple theoretical analysis of the algorithm which results in graphical guidelines for parameter selection. The user can thus take well-informed decisions according to the desired exploration–exploitation tradeoff: either favor explo- ration by a thorough sampling of the solution...
Website: bitbucket.org | Filesize: -
No of Page(s): 9
Download The particle swarm optimization algorithm: convergence ... - Bitbucket.pdf
performance on benchmark functions superior to previously published results are given. 2002 Elsevier Science B.V. All rights reserved. Keywords: Particle swarm optimization; Stochastic optimization; Analysis of algorithms; Parallel algorithms 1. Introduction The particle swarm optimization (PSO) is a paral- lel evolutionary computation technique developed by Kennedy and Eberhart [4] based on the social behav- ior metaphor. A standard textbook on PSO, treating both the social and computational paradigms, is [5]. The PSO algorithm is initialized with a population of random candidate solutions, conceptualized as parti- cles. Each particle is assigned a randomized velocity and is iteratively moved through the problem space. It is attracted towards the location of the best fitness achieved so far by the particle itself and by the loca- tion of the best fitness achieved so far across the whole population (global version of the algorithm). The PSO algorithm includes some tuning parame- ters that greatly influence the algorithm performance, E-mail address: trelea@grignon.inra.fr (I.C. Trelea). often stated as the exploration–exploitation tradeoff: Exploration is the ability to test various regions in the problem space in order to locate a good optimum, hopefully the global one. Exploitation is the ability to concentrate the search around a promising candidate solution in order to locate the optimum precisely. De- spite recent research efforts, the selection of the al- gorithm parameters remains empirical to a large ex- tent. A complete theoretical analysis of the algorithm has been given by Clerc and Kennedy [2]. Based on this analysis, the authors derived a reasonable set of tuning parameters, as confirmed by [3]. The reference [2] contains a good deal of mathematical complex- ity, however, and deriving from it simple user-oriented guidelines for the parameter selection in a specific problem is not straightforward. The present work gives some additional insight into the PSO parameter selection topic. It is estab- lished that some of the parameters add no flexibil- ity to the algorithm and can be discarded without 0020-0190/02/$ – see front matter 2002 Elsevier Science B.V. All rights reserved. PII: S0020-0190(02)00447-7 318 I.C. Trelea / Information Processing Letters 85 (2003) 317–325 loss of generality. Results from the dynamic system theory are used for a relatively simple theoretical analysis of the algorithm which results in graphical guidelines for parameter selection. The user can thus take well-informed decisions according to the desired exploration–exploitation tradeoff: either favor explo- ration by a thorough sampling of the solution...
Website: bitbucket.org | Filesize: -
No of Page(s): 9
Download The particle swarm optimization algorithm: convergence ... - Bitbucket.pdf
A Genetic Algorithm for Bin Packing and Line Balancing
Algorithm for BPP running in polynomial time (and there will most probably never be one). However, [Garey and The bin packing problem can be best described in Johnson,79] cite simple heuristics which can be shown to 'transportation' terms: given a set of boxes of different be no worse (but also no better) than a rather small sizes, how should one pack them all into containers of a multiplying factor above the optimal number of bins. The given size, in order to use as few containers as possible?
idea is straightforward: starting with one empty bin, take The task of balancing of (robotized) assembly the objects one by one and for each of them first search lines is of considerable industrial importance. It consists the bins so far used for a space large enough to of assigning operations from a given set to workstations in accommodate it. If such a bin can be found, put the object a production line in such a way that (1) no assembly there, if not, request a new bin. Putting the object into the precedence constraint is violated, (2) no workstation in the first available bin found yields the First Fit (FF) heuristic. line takes longer than a predefined cycle time to perform Searching for the most filled bin still having enough space all the tasks assigned to it, and (3) as few workstations as for the object yields the Best Fit, a seemingly better possible are needed to perform all the tasks in the set. heuristic, which can, however, be shown to perform as This paper presents a genetic grouping algorithm well (as bad) as the FF, while being slower. for the two problems. We first define the two problems precisely and 1.2 The Line Balancing specify a cost function suitable for the bin packing problem. The line balancing problem (LBP) can be descri- Next, we show why the classic genetic algorithm bed as follows: given a set of tasks of various lengths, performs poorly on grouping problems and then present an subject to precedence constraints (i.e. some tasks have as encoding of solutions fitting them. prerequisite the completion of one or more other tasks, see We present efficient crossover and mutation ope- [Sacerdoti,77]), and a time constant called cycle time , how rators for the bin packing. Then we give the modification should be the tasks distributed over workstations along a necessary to fit these operators for the line balancing. production (assembly) line, so that (1) no workstation We follow with results of performance tests on takes longer than the cycle time to complete all the tasks randomly generated data. Especially the line balancing assigned to it and (2) the precedence constraints are tests largely cover the real-world problem size. complied with? We conclude with a discussion of the results and In more formal terms, we define the LBP as the areas of further research. following decision problem: Given a...
Website: www.cse.hcmut.edu.vn | Filesize: -
No of Page(s): 7
Download A Genetic Algorithm for Bin Packing and Line Balancing.pdf
idea is straightforward: starting with one empty bin, take The task of balancing of (robotized) assembly the objects one by one and for each of them first search lines is of considerable industrial importance. It consists the bins so far used for a space large enough to of assigning operations from a given set to workstations in accommodate it. If such a bin can be found, put the object a production line in such a way that (1) no assembly there, if not, request a new bin. Putting the object into the precedence constraint is violated, (2) no workstation in the first available bin found yields the First Fit (FF) heuristic. line takes longer than a predefined cycle time to perform Searching for the most filled bin still having enough space all the tasks assigned to it, and (3) as few workstations as for the object yields the Best Fit, a seemingly better possible are needed to perform all the tasks in the set. heuristic, which can, however, be shown to perform as This paper presents a genetic grouping algorithm well (as bad) as the FF, while being slower. for the two problems. We first define the two problems precisely and 1.2 The Line Balancing specify a cost function suitable for the bin packing problem. The line balancing problem (LBP) can be descri- Next, we show why the classic genetic algorithm bed as follows: given a set of tasks of various lengths, performs poorly on grouping problems and then present an subject to precedence constraints (i.e. some tasks have as encoding of solutions fitting them. prerequisite the completion of one or more other tasks, see We present efficient crossover and mutation ope- [Sacerdoti,77]), and a time constant called cycle time , how rators for the bin packing. Then we give the modification should be the tasks distributed over workstations along a necessary to fit these operators for the line balancing. production (assembly) line, so that (1) no workstation We follow with results of performance tests on takes longer than the cycle time to complete all the tasks randomly generated data. Especially the line balancing assigned to it and (2) the precedence constraints are tests largely cover the real-world problem size. complied with? We conclude with a discussion of the results and In more formal terms, we define the LBP as the areas of further research. following decision problem: Given a...
Website: www.cse.hcmut.edu.vn | Filesize: -
No of Page(s): 7
Download A Genetic Algorithm for Bin Packing and Line Balancing.pdf
Thursday, September 27, 2012
Inhomogeneous Force-Directed Layout Algorithms in the - CiteSeer
Inhomogeneous Force-Directed Layout Algorithms in the Visualisation Pipeline: From Layouts to Visualisations Neville Churcher Warwick Irwin Carl Cook Software Visualistion Group, Department of Computer Science, University of Canterbury, Private Bag 4800, Christchurch, New Zealand E-mail: fneville,wal,c.cookg@cosc.canterbury.ac.nz Abstract The visualisation pipeline approach is a flexible and extensible technique for generating visualisations. The basic pipeline functions involve the capture and representation of data, the computation of geometry and the presentation of visual output. Data is rep- resented in XML at each stage
and is successively transformed, typically by XSLT transformations, as it moves through the pipeline. A force-directed lay- out engine, Angle is one of the major components in the computation of 2D and 3D geometry. In this paper, we describe inhomogeneous force models and their implementation in Angle. These allow a richer variety of properties and relationships of the under- lying graph and application domain to be included in the visualisation. We present examples from our software visualisation research. 1 Introduction Force-directed layout techniques, also known as spring embedders, (Eades 1983, Eades 1984, Di Bat- tista, Eades, Tamassia & Tollis 1999) are a reliable general-purpose tool for graph layout applications. Although other techniques may be capable of deliv- ering superior results for particular classes of graphs, force-directed methods have found application in a wide range of areas. In our work, we require layout algorithms which can reliably provide a satisfactory layout when pre- sented with an unknown graph. It is more important that our layouts be good enough all the time" than great some of the time". Force-directed methods generally exhibit smooth convergence to the nal lay- out con guration, making them particularly suitable for layouts which are presented dynamically to users via a graphical user interface. The remainder of the paper is structured as fol- lows. In the next section, we outline our visualisa- tion pipeline approach and describe the r^ole of An- gle (Churcher & Creek 2001), our layout engine. We introduce inhomogeneous force models in Section 3 and discuss our approach and its implementation in Section 4. We illustrate our approach by presenting some examples of its application in Section 5. Finally, our conclusions and discussion of work in progress are presented in Section 6. Copyright c©2004, Australian Computer Society, Inc. This pa- per appeared at the Australasian Symposium on Information Visualisation, Christchurch, 2004. Conferences in Research and Practice in Information Technology, Vol. ??. Neville Churcher and Clare Churcher, Ed. Reproduction for academic, not-for pro t purposes permitted provided this text is included. 2 Layout in the visualisation pipeline The conventional visualisation pipeline (Schroeder, Martin & Lorensen 1998, for example) consists of three basic phases: data capture/generation & pro- cessing; computation of geometry and rendering of the resulting visualisation. Our recent work in information and software vi- sualisation (Churcher, Keown & Irwin 1999, Irwin & Churcher 2002, Churcher, Irwin & Kriz 2003, Irwin & Churcher 2003) involves a...
Website: ir.canterbury.ac.nz | Filesize: -
No of Page(s): 9
Download Inhomogeneous Force-Directed Layout Algorithms in the - CiteSeer.pdf
and is successively transformed, typically by XSLT transformations, as it moves through the pipeline. A force-directed lay- out engine, Angle is one of the major components in the computation of 2D and 3D geometry. In this paper, we describe inhomogeneous force models and their implementation in Angle. These allow a richer variety of properties and relationships of the under- lying graph and application domain to be included in the visualisation. We present examples from our software visualisation research. 1 Introduction Force-directed layout techniques, also known as spring embedders, (Eades 1983, Eades 1984, Di Bat- tista, Eades, Tamassia & Tollis 1999) are a reliable general-purpose tool for graph layout applications. Although other techniques may be capable of deliv- ering superior results for particular classes of graphs, force-directed methods have found application in a wide range of areas. In our work, we require layout algorithms which can reliably provide a satisfactory layout when pre- sented with an unknown graph. It is more important that our layouts be good enough all the time" than great some of the time". Force-directed methods generally exhibit smooth convergence to the nal lay- out con guration, making them particularly suitable for layouts which are presented dynamically to users via a graphical user interface. The remainder of the paper is structured as fol- lows. In the next section, we outline our visualisa- tion pipeline approach and describe the r^ole of An- gle (Churcher & Creek 2001), our layout engine. We introduce inhomogeneous force models in Section 3 and discuss our approach and its implementation in Section 4. We illustrate our approach by presenting some examples of its application in Section 5. Finally, our conclusions and discussion of work in progress are presented in Section 6. Copyright c©2004, Australian Computer Society, Inc. This pa- per appeared at the Australasian Symposium on Information Visualisation, Christchurch, 2004. Conferences in Research and Practice in Information Technology, Vol. ??. Neville Churcher and Clare Churcher, Ed. Reproduction for academic, not-for pro t purposes permitted provided this text is included. 2 Layout in the visualisation pipeline The conventional visualisation pipeline (Schroeder, Martin & Lorensen 1998, for example) consists of three basic phases: data capture/generation & pro- cessing; computation of geometry and rendering of the resulting visualisation. Our recent work in information and software vi- sualisation (Churcher, Keown & Irwin 1999, Irwin & Churcher 2002, Churcher, Irwin & Kriz 2003, Irwin & Churcher 2003) involves a...
Website: ir.canterbury.ac.nz | Filesize: -
No of Page(s): 9
Download Inhomogeneous Force-Directed Layout Algorithms in the - CiteSeer.pdf
Distributed Force-Directed Graph Layout and Visualization
Eurographics Symposium on Parallel Graphics and Visualization (2006) Alan Heirich, Bruno Raffin, and Luis Paulo dos Santos (Editors) Distributed Force-Directed Graph Layout and Visualization ChristopherMueller, DouglasGregor, AndrewLumsdaine Open Systems Laboratory Indiana University Bloomington, IN 47405 {chemuell,dgregor,lums}@osl.iu.edu Abstract While there exist many interactive tools for the visualization of small graphs and networks, these tools do not address the fundamental problems associated with the visualization of large graphs. In particular,larger graphs require much larger display areas (e.g., display walls) to reduce visual
clutter, allowing users to determine the structure of large graphs. Moreover, the layout algorithms employed by these graph visualization tools do not scale to larger graphs, thereby forcing users into a batch- oriented process of generating layouts offline and later viewing of static graph images. In this paper, we present a parallel graph layout algorithm based on the Fruchterman-Reingold force-directed layout algorithm and demonstrate its implementation in a distributed rendering environment.The algorithm uses availabledistributed resources for both compute and renderingtasks, animating the graph as the layout evolves. We evaluatethe algorithm for scalabilityand interactivity and discuss variations that minimize communication for specific types of graphs and applications. 1. Introduction The visualization of large graphsis becoming increas- ingly important in diverse fields including bioinfor- matics, socialnetworkanalysis, andnetwork optimiza- tion (e.g., [ADWM04].However, visualization of large graphs is typically a batch-oriented, sequential pro- cess: users must first constructa layout offline, which can easily require tens of minutes to compute.Users can then view the resulting static image on a single display or display wall. This situationstandsin stark contrast to the plethora of visualization tools [JM04] for small graphs that produce animated, interactive layouts on single workstations. Early results with vi- sualizing dense graphs on large surfacessuggest that they “qualitatively [change] interactive network visu- alization” [AKGN99]. Visualization tools for small graphs do not scale well to larger graphs for two reasons. The first rea- son is that the graph layout algorithms themselves rarely scale well. For instance,many of thesetools use force-directed layout algorithms, which determine the position of each node in a graph by iteratively com- putingattractive forces between connectednodes and repulsive forcesbetweenall pairsof nodes.While these algorithms are ideal for animation—thevisualization systemcan display the graphafter each iteration—the force calculations are expensive and can easily take several secondsper iteration on medium-sized graphs, making them unacceptablyslow for interactive use. The second reason that small-graph visualization tools cannotscale to largergraphsis that few of these toolsprovidesupportfordistributedrenderingto large format display devices such as tiled display walls. Graphvisualizationsare visually limitedby the num- ber of nodes and edges that can be rendered on the display. The node-link graph diagramdisplays nodes as points or glyphs and edges as lines between the nodes. On most displays, only a few hundred edges can be effectively displayed before the image becomes too clutteredto interpret. While techniques exist for c© The Eurographics Association 2006. C. Mueller et al / Distributed Force-Directed Graph Layout and Visualization improving the layout...
Website: osl.iu.edu | Filesize: -
No of Page(s): 8
Download Distributed Force-Directed Graph Layout and Visualization.pdf
clutter, allowing users to determine the structure of large graphs. Moreover, the layout algorithms employed by these graph visualization tools do not scale to larger graphs, thereby forcing users into a batch- oriented process of generating layouts offline and later viewing of static graph images. In this paper, we present a parallel graph layout algorithm based on the Fruchterman-Reingold force-directed layout algorithm and demonstrate its implementation in a distributed rendering environment.The algorithm uses availabledistributed resources for both compute and renderingtasks, animating the graph as the layout evolves. We evaluatethe algorithm for scalabilityand interactivity and discuss variations that minimize communication for specific types of graphs and applications. 1. Introduction The visualization of large graphsis becoming increas- ingly important in diverse fields including bioinfor- matics, socialnetworkanalysis, andnetwork optimiza- tion (e.g., [ADWM04].However, visualization of large graphs is typically a batch-oriented, sequential pro- cess: users must first constructa layout offline, which can easily require tens of minutes to compute.Users can then view the resulting static image on a single display or display wall. This situationstandsin stark contrast to the plethora of visualization tools [JM04] for small graphs that produce animated, interactive layouts on single workstations. Early results with vi- sualizing dense graphs on large surfacessuggest that they “qualitatively [change] interactive network visu- alization” [AKGN99]. Visualization tools for small graphs do not scale well to larger graphs for two reasons. The first rea- son is that the graph layout algorithms themselves rarely scale well. For instance,many of thesetools use force-directed layout algorithms, which determine the position of each node in a graph by iteratively com- putingattractive forces between connectednodes and repulsive forcesbetweenall pairsof nodes.While these algorithms are ideal for animation—thevisualization systemcan display the graphafter each iteration—the force calculations are expensive and can easily take several secondsper iteration on medium-sized graphs, making them unacceptablyslow for interactive use. The second reason that small-graph visualization tools cannotscale to largergraphsis that few of these toolsprovidesupportfordistributedrenderingto large format display devices such as tiled display walls. Graphvisualizationsare visually limitedby the num- ber of nodes and edges that can be rendered on the display. The node-link graph diagramdisplays nodes as points or glyphs and edges as lines between the nodes. On most displays, only a few hundred edges can be effectively displayed before the image becomes too clutteredto interpret. While techniques exist for c© The Eurographics Association 2006. C. Mueller et al / Distributed Force-Directed Graph Layout and Visualization improving the layout...
Website: osl.iu.edu | Filesize: -
No of Page(s): 8
Download Distributed Force-Directed Graph Layout and Visualization.pdf
Effect of Fuzzy Logic Controller
Advanced intelligent control design cannot entirely replace the application of conventional controller in robotic system. On the other hand, intelligent controllers can be implemented into conventional controller design to increase its performance and ability. Most of intelligent control in movement control involves fuzzy logic and neural network system. This study features the influence
of fuzzy logic controller upon the performance of robot movement simulation, which is controlled by a digital controller. Model design and simulation are done in SIMULINK, using Fuzzy Logic Toolbox provided by MATLAB software to control the movement speed of a robotic designed system. Finally, the movement speed is found better off controlled with the additional of fuzzy logic controller instead of the digital controller solely. Keywords: Intelligent Control, Fuzzy Logic, Digital Controller, Robot Movement, Simulink. INTRODUCTION Robotics system design is becoming one of challenging tasks for engineers. Moving toward the technology of artificial intelligent robotic designed system, software simulations and control is very important before engineers can proceed with the mechanical and electronic construction of the whole system [1]. Design and development in robotic system has become an important field in engineering industries due to the requirement of high performance autonomous machine to increase production and handle duty under tough environment In the development of artificial intelligent human bases robotic design system, fuzzy logic controller is very important when dealing with uncertainty in the working condition. Unknown moving path condition and imprecise input signal are two common problems that occur in the real world robot operations. Because of this, fuzzy logic controller is implemented to the system design in order to handle these conditions. A few robotic fuzzy logic controlled design done by previous researcher with various application can be found in [2],[3],[4],[5],[6],[7]. In this research, the system is specifically designed to define the robotic movement. Generally, the design task can be divided into movement system, sensors system, power system, controller circuits and mechanical construction of the robot. However, only movement, sensor and controller system designs are involved in this simulation. Robotic movement system can KATHMANDU UNIVERSITY JOURNAL OF SCIENCE, ENGINEERING AND TECHNOLOGY VOL. I, No. V, SEPTEMBER 2008, pp 28-39. 29 be designed using DC servo motors, AC motor or pneumatic system. Motors are normally used for joint and robot’s wheel construction because of its small size and easier to control. With the fuzzy logic control blocks [8], the designed system can be improved so that it can handle imprecise signals which are very common in the real world. Whenever the signals alter, the speed of the robotic system is adjusted using the fuzzy logic controller to give an appropriate movement correction defined for the whole system. Simulation and analysis of this robotic movement control system provide designer...
Website: www.ku.edu.np | Filesize: -
No of Page(s): 12
Download EFFECT OF FUZZY LOGIC CONTROLLER
of fuzzy logic controller upon the performance of robot movement simulation, which is controlled by a digital controller. Model design and simulation are done in SIMULINK, using Fuzzy Logic Toolbox provided by MATLAB software to control the movement speed of a robotic designed system. Finally, the movement speed is found better off controlled with the additional of fuzzy logic controller instead of the digital controller solely. Keywords: Intelligent Control, Fuzzy Logic, Digital Controller, Robot Movement, Simulink. INTRODUCTION Robotics system design is becoming one of challenging tasks for engineers. Moving toward the technology of artificial intelligent robotic designed system, software simulations and control is very important before engineers can proceed with the mechanical and electronic construction of the whole system [1]. Design and development in robotic system has become an important field in engineering industries due to the requirement of high performance autonomous machine to increase production and handle duty under tough environment In the development of artificial intelligent human bases robotic design system, fuzzy logic controller is very important when dealing with uncertainty in the working condition. Unknown moving path condition and imprecise input signal are two common problems that occur in the real world robot operations. Because of this, fuzzy logic controller is implemented to the system design in order to handle these conditions. A few robotic fuzzy logic controlled design done by previous researcher with various application can be found in [2],[3],[4],[5],[6],[7]. In this research, the system is specifically designed to define the robotic movement. Generally, the design task can be divided into movement system, sensors system, power system, controller circuits and mechanical construction of the robot. However, only movement, sensor and controller system designs are involved in this simulation. Robotic movement system can KATHMANDU UNIVERSITY JOURNAL OF SCIENCE, ENGINEERING AND TECHNOLOGY VOL. I, No. V, SEPTEMBER 2008, pp 28-39. 29 be designed using DC servo motors, AC motor or pneumatic system. Motors are normally used for joint and robot’s wheel construction because of its small size and easier to control. With the fuzzy logic control blocks [8], the designed system can be improved so that it can handle imprecise signals which are very common in the real world. Whenever the signals alter, the speed of the robotic system is adjusted using the fuzzy logic controller to give an appropriate movement correction defined for the whole system. Simulation and analysis of this robotic movement control system provide designer...
Website: www.ku.edu.np | Filesize: -
No of Page(s): 12
Download EFFECT OF FUZZY LOGIC CONTROLLER
The Genetic Algorithm in Computer Science - MIT Mathematics
The Genetic Algorithm in Computer Science Eric Krevice Prebys Abstract. The genetic algorithm is described, including its three main steps: selection, crossover, and mutation. This description is used in the presentation of two methods for analyzing genetic algorithms: schema analysis and mathematical modeling. The discus- sion of schema analysis focuses on the Schema Theorem. Following it, an exact mathe- matical model is described. First, the model is presented assuming an in nite population. Then the model is made more accurateby assuming a nite population. 1. Introduction. All life on Earth is thought to evolve. Genetic algorithms are com- puting algorithms constructed in analogy with the process of evolution [1]. Genetic algorithms seem to be useful for searching very general spaces and poorly de ned spaces. It is hoped that, through more rigorous theoretical study, we will determine what sorts of spaces genetic algorithms can search e ciently. In biology, the gene is the basic unit of genetic storage [5]. Within cells, genes are strung together to form chromosomes. The simplest possible sexual reproduction is between single-cell organisms. The two cells fuse to produce a cell with two sets of chromosomes, called a diploid cell. The diploid cell immediately undergoes meiosis. In meiosis, each of the chromosomes in the diploid cell makes an exact copy of itself. Then the chromosome groups (original and copy) undergo crossover with the corresponding groups, mixing the genes somewhat. Finally the chromosomes separate twice, giving four haploid cells. Mutation can occur at any stage, and any mutation in the chromo- somes will be inheritable. Mutation is essential for evolution. There are three types relevant to genetic algorithms: point mutations where a single gene is changed, chromo- somal mutations where some number of genes are lost completely, and inversion where a segment of the chromosome becomes ipped. ThispaperfollowsMelanieMitchell’sbook[3]. Wewillintroduceasimpli edgenetic algorithm using the notions of sexual reproduction. This algorithm captures most of the essential components of every genetic algorithm, so we will call it the Standard Genetic Algorithm. A simple way to view the Standard Genetic Algorithm is provided by schema. With them we can understand the Schema Theorem. It explains how crossover allows a genetic algorithm to zero in on an optimal solution. However, schema are inadequate in determining some characteristics of the population. Speci cally, in determining the speed of population convergence, and the distribution of the population over time. To deal with these issues, we will develop an exact mathematical model, rst assuming an in nite population, and then a nite population. This model was originally presented by Michael Vose and G.E. Liepins in [2] and [7]. More details are found in two papers by Allen Nix and Michael Vose, [4] and [8]. In practice, the genetic algorithms used are much more complex then the Standard Genetic Algorithm. Consequently, the analyses presented in this paper have some major weaknesses. Speci cally, schema analysis...
Website: www-math.mit.edu | Filesize: -
No of Page(s): 6
Download The Genetic Algorithm in Computer Science - MIT Mathematics.pdf
A fast and elitist multiobjective genetic algorithm
182 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 6, NO. 2, APRIL 2002 A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II Kalyanmoy Deb, Associate Member, IEEE, Amrit Pratap, Sameer Agarwal, and T. Meyarivan Abstract—Multiobjective evolutionary algorithms (EAs) that use nondominated sorting and sharing have been criti- cized mainly for their: 1) 40 51 41 computational complexity (where is the number of objectives and is the population size); 2) nonelitism approach; and 3) the need for specifying a sharing parameter. In this
paper, we suggest a nondominated sorting-based multiobjective EA (MOEA), called nondominated sorting genetic algorithm II (NSGA-II), which alleviates all the above three difficulties. Specifically, a fast nondominated sorting approach with 40 50 41 computational complexity is presented. Also, a selection operator is presented that creates a mating pool by combining the parent and offspring populations and selecting the best (with respect to fitness and spread) solutions. Simulation results on difficult test problems show that the proposed NSGA-II, in most problems, is able to find much better spread of solutions and better convergence near the true Pareto-optimal front compared to Pareto-archived evolution strategy and strength-Pareto EA—two other elitist MOEAs that pay special attention to creating a diverse Pareto-optimal front. Moreover, we modify the definition of dominance in order to solve constrained multiobjective problems efficiently. Simulation results of the constrained NSGA-II on a number of test problems, including a five-objective seven-constraint nonlinear problem, are compared with another constrained multiobjective optimizer and much better performance of NSGA-II is observed. Index Terms—Constraint handling, elitism, genetic algorithms, multicriterion decision making, multiobjective optimization, Pareto-optimal solutions. I. INTRODUCTION T HE PRESENCE of multiple objectives in a problem, in principle, gives rise to a set of optimal solutions (largely known as Pareto-optimal solutions), instead of a single optimal solution. In the absence of any further information, one of these Pareto-optimal solutions cannot be said to be better than the other. This demands a user to find as many Pareto-optimal solu- tions as possible. Classical optimization methods (including the multicriterion decision-making methods) suggest converting the multiobjective optimization problem to a single-objective opti- mization problem by emphasizing one particular Pareto-optimal solution at a time. When such a method is to be used for finding multiple solutions, it has to be applied many times, hopefully finding a different solution at each simulation run. Over the past decade, a number of multiobjective evolu- tionary algorithms (MOEAs) have been suggested [1], [7], [13], Manuscript received August 18, 2000; revised February 5, 2001 and September 7, 2001. The work of K. Deb was supported by the Ministry of Human Resources and Development, India, under the Research and Development Scheme. The authors are with the Kanpur Genetic Algorithms Laboratory, Indian In- stitute of Technology, Kanpur PIN 208 016, India (e-mail: deb@iitk.ac.in). Publisher Item Identifier S 1089-778X(02)04101-2. [20], [26]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single simulation...
Website: www.iitk.ac.in | Filesize: -
No of Page(s): 16
Download A fast and elitist multiobjective genetic algorithm: NSGA-II ....pdf
paper, we suggest a nondominated sorting-based multiobjective EA (MOEA), called nondominated sorting genetic algorithm II (NSGA-II), which alleviates all the above three difficulties. Specifically, a fast nondominated sorting approach with 40 50 41 computational complexity is presented. Also, a selection operator is presented that creates a mating pool by combining the parent and offspring populations and selecting the best (with respect to fitness and spread) solutions. Simulation results on difficult test problems show that the proposed NSGA-II, in most problems, is able to find much better spread of solutions and better convergence near the true Pareto-optimal front compared to Pareto-archived evolution strategy and strength-Pareto EA—two other elitist MOEAs that pay special attention to creating a diverse Pareto-optimal front. Moreover, we modify the definition of dominance in order to solve constrained multiobjective problems efficiently. Simulation results of the constrained NSGA-II on a number of test problems, including a five-objective seven-constraint nonlinear problem, are compared with another constrained multiobjective optimizer and much better performance of NSGA-II is observed. Index Terms—Constraint handling, elitism, genetic algorithms, multicriterion decision making, multiobjective optimization, Pareto-optimal solutions. I. INTRODUCTION T HE PRESENCE of multiple objectives in a problem, in principle, gives rise to a set of optimal solutions (largely known as Pareto-optimal solutions), instead of a single optimal solution. In the absence of any further information, one of these Pareto-optimal solutions cannot be said to be better than the other. This demands a user to find as many Pareto-optimal solu- tions as possible. Classical optimization methods (including the multicriterion decision-making methods) suggest converting the multiobjective optimization problem to a single-objective opti- mization problem by emphasizing one particular Pareto-optimal solution at a time. When such a method is to be used for finding multiple solutions, it has to be applied many times, hopefully finding a different solution at each simulation run. Over the past decade, a number of multiobjective evolu- tionary algorithms (MOEAs) have been suggested [1], [7], [13], Manuscript received August 18, 2000; revised February 5, 2001 and September 7, 2001. The work of K. Deb was supported by the Ministry of Human Resources and Development, India, under the Research and Development Scheme. The authors are with the Kanpur Genetic Algorithms Laboratory, Indian In- stitute of Technology, Kanpur PIN 208 016, India (e-mail: deb@iitk.ac.in). Publisher Item Identifier S 1089-778X(02)04101-2. [20], [26]. The primary reason for this is their ability to find multiple Pareto-optimal solutions in one single simulation...
Website: www.iitk.ac.in | Filesize: -
No of Page(s): 16
Download A fast and elitist multiobjective genetic algorithm: NSGA-II ....pdf
Subscribe to:
Posts (Atom)