Coulomb propulsion has been proposed for spacecraft cluster applications with separation distances on the order of dozens of meters. This thesis presents an investigation of analytic charge solutions for a planar and three dimensional four satellite formations. The solutions are formulated in terms of the formation geometry. In contrast to the two and three spacecraft Coulomb formations, a four spacecraft formation has additional constraints that need to be satisfied for the individual charges on the spacecraft to be unique and real. A spacecraft must not only satisfy the previously developed inequality constraints to yield a real charge solution, but it must also satisfy three additional equality constraints to ensure the spacecraft charge is unique. Further, a method is presented to reduce the number of equality constraints arising due the dynamics of a four spacecraft formation. Formation geometries are explored to determine the feasibility of orienting a square formation arbitrarily in any given plane. The unique and real spacecraft charges are determined as functions of the orientation of the square formation in a given principal orbit plane. For a three-dimensional tetrahedron formation, the charge products obtained are a unique set of solution. The full three-dimensional rotation of a tetrahedron is reduced to a two angle rotation for simpler analysis. The number of equality constraints for unique spacecraft charges can not be reduced for a three-dimensional formation. The two angle rotation results are presented for different values of the third angle. The thesis also presents the set up for a co-linear four-craft problem. The solution for the co-linear formation is not developed. The discussion of co-linear formations serves as an open question on how to determine analytic solutions for system with null-space dimension greater than 1. The thesis also presents a numerical tool for determining potential shapes of a static Coulomb formation as a support to the analytical solutions. The numerical strategy presented here uses a distributed Genetic Algorithm (GA) as an optimization tool. The GA offers several advantages over traditional gradient based optimization methods. Distributing the work of the GA over several processors reduces the computation time to arrive at a solution. The thesis discusses the implementation of a distributed GA used in the analysis of a static Coulomb formation. The thesis also addresses the challenges of implementation of a distributed GA on a computing cluster and presents candidate solutions. / Master of Science

Genetic Algorithms (GAs) are search algorithms inspired by genetics and natural selection, and have been used to solve difficult problems in many disciplines, including modelling, control systems and automation. GAs are generally able to find good solutions in reasonable time, however as they are applied to larger and harder problems they are very demanding in terms of computation time and memory. The Internet is the most powerful parallel and distributed computation environment in the world, and the idle cycles and memories of computers on the Internet have been increasingly recognized as a huge untapped source of computation power. By combining Internet computing and GAs, this dissertation provides a framework for Internet-based parallel and distributed GAs that gives scientists and engineers an easy and affordable way to solve hard real world problems. Developing parallel computation applications on the Internet is quite unlike developing applications in traditional parallel computation environments, such as multiprocessor systems and clusters. This is because the Internet is different in many respects, such as communication overhead, heterogeneity and volatility. To develop an Internet-based GA, we need to understand the implication of these differences. For this purpose, a convergence model for heterogenous and volatile networks is presented and used in experiments that study GA performance and robustness in Internet-like scenarios. The main outcome of this research is an Internet-based distributed GA framework called G2DGA. G2DGA is an island model distributed GA, which can provide support for big populations needed to solve many real world problems. G2DGA uses a novel hybrid peer-to-peer (P2P) design with island node activity coordinated by supervisor nodes that offer a global overview of the GA search state. Compared to client/server approaches, the P2P architecture improves scalability and fault tolerance by allowing direct communication between the islands and avoiding single-point-of-failure situations. One of the defining characteristics of Internet computing is the dynamics and volatility of the environment, and a parallel and distributed GA that does not adapt to its environment cannot use the available resources efficiently. Two novel adaptive methods are investigated. The first method is migration topology adaptation, which uses clustering on elite individuals from each island to rebuild the migration topology. Experiments with the migration topology adapter show that it gives G2DGA better performance than a GA with static migration topology of a similar or larger connectivity level. The second method is population size adaptation, which automatically finds the number of islands and island population sizes needed to solve a given problem efficiently. Experiments on the population size adapter show that it is robust, and compares favourably with the traditional trial-and-error approach in terms of computational effort and solution quality. The scalability and robustness of G2DGA has been extensively tested in network scenarios of varying volatility and heterogeneity. Experiments with up to 60 computers were conducted in computer laboratories, while more complex network scenarios have been studied in an Internet simulator. In the experiments, G2DGA consistently performs as well as, and usually significantly better than, static distributed GAs and the difference grows larger with increased network instability. The results show that G2DGA, by continuously adjusting the migration policy and the population size, can detect and make efficient use of idle cycles donated over volatile Internet connections. To demonstrate that G2DGA can be used to implement and solve real world problems, a challenging application in VLSI design was developed and used in the testing of the framework. The application is a multi-layer floorplanner, which uses a novel GA representation and operators based on a slicing structure approach. Its packing quality compares favourably with other multi-layer floorplanners found in the literature. Internet-based distributed GA research is exciting and important since it enables GAs to be applied to problem areas where resource limitations make traditional approaches unworkable. G2DGA provides a scalable and robust Internet-based distributed GA framework that can serve as a foundation for future work in the field.