Evo-DesignOpt

Hierarchical Genetic Algorithms for Parallelization of Sparse Matrix Algebra
	High performance computing on a multicore processor demands efficient parallelization. While dense matrices can be efficiently distributed among cores without concern for inter-chip transport costs, sparse matrix algebra requires consideration of data distribution and transport costs. In collaboration with Lincoln Labs, we have teamed a hierarchical GA with a fine grained computation model. The GAs (inner and outer) adaptively determine an efficient processor mapping for sparse matrix multiplication with respect to data processing and transport costs. Nadya Travinin Bliss, Sanjeev Mohindra, V. Aggarwal, U.M. O'Reilly, "Analysis and Mapping of Sparse Matrix Computations," Proceedings of High Performance Embedded Computing, (HPEC 2007)
Motivation	Research in this vein facilitates migration of knowledge-based data-interpretation algorithms closer toward signal/data sources. Shortening the span between data collection and its interpretation forestalls data waste by processing it in a timely manner.
Applications	Surveillance, anomaly detection, security, transport, logistics, networks
Status	Active. Funded by MIT Lincoln Labs.

Genetic Algorithms for Network Coding
	Minimization of resources required for network coding is an NP-hard problem. We have designed scalable genetic algorithms to solve the problem for the multi-cast scenario. The NWC-GA incorporates network topological knowledge in its representation and adaptive operators. M. Kim, M. Médard, V. Aggarwal, U.M. O'Reilly, W. Kim, C.W. Ahn, M. Effros, "On Evolutionary Approaches to Minimizing Network Coding Resources,," 26th Annual IEEE Conference on Computer Communications (INFOCOM 2007) We have developed a NWC-GA for a distributed network and the multiple-unicast scenario that is embedded spatially (on the network being coded) and temporally. (see GECCO 2007 publication) We have developed a Multi-objective GA that provides pareto-front tradeoff options between coding and link costs. (see MILCOMM 2007 publication) To achieve practical network coding, we are addressing resource and throughput tradeoffs in additional multi and unicast scenarios. Collaborator: Prof. Muriel Médard, LIDS, MIT
Motivation	Network coding is an alternative to conventional network routing.
Applications	wireless and wired networks, sensor networks, ad-hoc networks
Status	Active.

Efficient, Scalable Evolutionary Algorithms for Multi-Objective Optimization Problems
	We are investigating how design knowledge can easily be elicited from an expert designer to be exploited by an algorithm that returns to the designer a suite of pareto-optimal (i.e. non-dominated) designs. These designs present different tradeoffs with respect to multiple objectives and allow the designer or control algorithm to choose between them. The choice can be updated according to the current critical performance specifications. The technical challenge is to efficiently explore the space of possible solutions with scalable techniques that accomodate high dimensionality and multiple objectives. V. Aggarwal, U.M. O'Reilly, COSMO: a correlation sensitive mutation operator for multi-objective optimization, Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation (GECCO '07) Minkyu Kim, Muriel Médard, Varun Aggarwal, and Una-May O'Reilly, On the Coding-Link Cost Tradeoff in Multicast Network Coding,2007 Military Communications Conference (MILCOM 2007)
Motivation	Complex, real-world optimization problems frequently have multiple objectives in combination with high design dimensionality. Changing circumstances imply that a suite of tradeoff solutions be available.
Applications	Analog circuit sizing and network coding (to tradeoff link cost and coding cost). Other potential domains include (but are not restricted to) transportation, network mgmt, finance, and logistics.
Status	Active.

Models that Leverage Convex Optimization Derived by A Hybrid Machine Learning and Evolutionary Algorithm
	Convex optimization techniques such as geometric programming and semi-definite programming are powerful techniques for design and optimization. However, they require the design problem to be modeled with a specific formulation such as a posynomial/monomial objective, constraint or sum-of-squares objective. This is often not straight forward to accomplish accurately. We investigate the use of machine learning and evolutionary algorithms for computing models supporting convex optimization techniques. We have developed a general hybrid EA+ML approach to model-building that accelerates the effectiveness of convex optimization. V. Aggarwal, U.M. O'Reilly, "Simulation-based reusable posynomial models for MOS transistor parameters" , Proceedings of the Conference on Design, Automation and Test in Europe, (DATE 2007)
Motivation	Our techniques fall into the set of hybrid search-based machine-learning methods capable of solving the general problem classes of classification and regression.
Applications	Widespread: eg, bioinformatics, surveillance, data mining, circuit design. Geometric and semi-definite programming are used in engineering design, operations research, coding theory, management science, economics, marketing, etc.
Status	Circuit focus in wrap up. Forthcoming report on approximation error bound.

Evolutionary Algorithms for Analog Reconfigurable Systems
	Model-free methods such as evolutionary algorithms allow reconfigurable systems to adapt or self-tune based solely on performance feedback. Analog reconfigurable systems have potential payoffs in two areas: Systems which need to be tuned or self-adapt according to a dynamic environment which is prohibitive to modeling; Facilitating post fabrication tuning of analog systems with high yield and low power objectives. Terry, Marcus, Farrell, Aggarwal, O'Reilly, GRACE: Generative Robust Analog Circuit Design, Applications of Evolutionary Computing, EvoWorkshops 2006, (EvoHOT). Aggarwal, Mao, O'Reilly, A Self-Tuning Analog Proportional-Integral-Derivative (PID) Controller, Adaptive Hardware Systems, 2006. White Paper
Status	Inactive. Sponsorship invited.

Adaptive Resource Allocation
	Computer architecture and application complexity is rapidly increasing. With the adoption of multi-core processors for desktop computing, workloads are less predictable because applications are more complex in terms of thread parallelism and diverse computation demands. Decentralized adaptive strategies within the operating system or runtime system potentially are a scalable solution to handling this complexity. We investigate computational economic mechanisms that allow individual software components to introspect on performance and adapt their run time resource requests like they would in a market place of sellers and consumers. Dynamic Load-Balancing of StreamIt Cluster Computations, Eric Fellheimer, MIT M.Eng Thesis, Advisor: Una-May O'Reilly Collaborators: Rodric Rabbah, Saman Amarasinghe, Steve Ward Funded under DARPA ACIP Phase 1.
Status	Inactive. Sponsorship invited.

Genr8: A design tool embedded in Maya for architects, Genr8 allows a designer to evolve computational generative processes that ``grow'' digital surfaces. Growth occurs within a 3D digital environment and responds to attractors, repellers and boundaries of the environment. More...

Genetic Programming for Compiler Design: Dissatisfaction with compiler efficiency and design, combined with the realization that compiler designers are overwhelmed with countless nonlinearly complex considerations motivated us to examine different passes within a compiler and their heuristics. We found a common, easily learned feature in the heuristics that we term a `priority function'. We used GP to generate more effective priority functions than currently exist in compilers. We optimized the priority functions associated with register allocation and branch removal via predication. More...

Genetic Programming Population Sizing Theory: This work attempted started addressing the lack of theory available to genetic programming practitioners to guide them in sizing a population for real problems. It analyzed building block supply in the initial population of a genetic programming run and based on a building block perspective derived a population sizing relationship for genetic programming.

Artificial Ants for Non-Photorealistic Rendering: An application of artificial ant techniques to the area of computer graphics known as Non-Photorealistic Rendering (NPR). An artificial ant colony placed on the environment of a digital image transforms a photograph into a stylized picture inspired by traditional artistry.

Typically Known	Less Heard Of
they determine "good enough" solutions in the class of NP-hard or NP-complete problems	they solve machine learning problems by recasting them as search problems
they optimize without needing gradient information or analytic functions	they learn model structure as well as parameters (Genetic Programming)
they naturally parallelize	they solve distributed problems requiring heterogenous or homogenous sub-solutions
they easily incorporate and leverage expert knowledge of the problem domain	they are naturally robust for soft computing

Evolvable Hardware: Artificial Life
	We have developed an evolvable hardware testbench named GRACE. Grace's software component includes an evolutionary algorithm that generates sized analog circuit topologies. Evolved circuit designs are directly tested in silicon. They are each dynamically configured on an Field Programmable Analog Array then exercised with input signal while their output behaviour is captured and evaluated. GRACE is extensible. We plan to pursue using a highly complex reconfigurable circuit environment to evolve complex circuits such as an ADC. Terry, Marcus, Farrell, Aggarwal, O'Reilly, GRACE: Generative Robust Analog Circuit Design, Proceedings of Applications of Evolutionary Computing, EvoWorkshops 2006: (EvoHOT),
Status	Inactive. Sponsorship invited.