Practical issues concerning the implementation and application of genetic algorithms to a number of optimisation problems are the main subjects dealt with in this thesis. Genetic algorithms (GAs) are an attractive class of computational models that attempt to mimic the mechanisms of natural evolution to solve problems in a wide variety of domains. A general purpose genetic algorithm toolkit is developed and applied to the Steiner Problem in Graphs and the Radio Link Frequency Assignment Problem. The toolkit is then extended to cover a large number of parallel genetic algorithm models which are then compared. Solutions for the two case studies are presented with each of the parallel GAs. The thesis begins with a general introduction to genetic algorithms. Holland's original genetic algorithm is described and it's workings illustrated on a simple function minimisation problem. The notion of a schema or similarity template as a basic building block in genetic algorithms is introduced and the schema theory presented. A description of important theoretical results is given and the introduction to genetic algorithms continues with practical issues that are dealt with in the second chapter. The basic components of a modern genetic algorithm are outlined and examples for important components, as found in the Jiterature, are given. The second chapter concludes with the description of a number of applications of genetic algorithms to areas such as function optimisation, combinatorial optimisation, genetic programming, process control and classifier systems. In Chapter 3, the sequential GA toolkit, GAmeter, is described. The General Search paradigm around which the toolkit is implemented is introduced. Notable characteristics of the genetic algorithms kernel and the user interface are mentioned. A popular function optimisation problem is used to illustrate important aspects of genetic algorithms and aspects specific to the toolkit. The Steiner Tree problem in graphs is the first of two case studies examined in detail in this thesis. This is a popular NP-complete problem with a range of applications in areas such as communications, scheduling and printed circuit design. A survey of standard techniques, such as simplification methods, exact algorithms and heuristics is given. Two possible representations for solving it using genetic algorithms are described and applied to a well-known set of problems. Chapter 4 concludes with a comparison of the best GA technique with other heuristics for this problem. The Radio Link Frequency Assignment Problem, described in Chapter 5, is the second case study investigated in this thesis. Genetic algorithms were applied to this problem as part of a EUCLID (European Cooperation for the Long Term in Defence) funded multi-national study to compare exact and heuristic techniques for hard combinatorial problems associated with military applications. A number of approaches used to solve this highly constrained, hard problem for genetic algorithms are described. These include a range of new genetic operators and catalytic terms that are added to the fitness function. Apart from the direct approach to solving this problem using genetic algorithms, for which the majority of operators and catalytic terms apply, an indirect approach which combines genetic algorithms with backtracking is described. The possibility of using a meta genetic algorithm to chose the best of a multitude of options, e.g. genetic operators and parameter settings for a GA applied to the Radio Link Frequency Assignment Problem is investigated. Results are reported for two sets of problems that were used by all participants in this project. An overview of the techniques investigated for this project is given and the chapter concludes with comparisons between all these techniques. In Chapter 6, an overview of general aspects in parallel processing is given. Parallel computer architectures, parallel programming paradigms and performance measurement are the main subjects dealt with in this chapter. Special emphasis is given to material relevant to the investigation on parallel genetic algorithms, presented in the following chapter. In Chapter 7, parallel genetic algorithms are examined in some detail. A number of parallel GA models are described and classified according to whether they are designed around the sequential GA or around a more natural model. A ParallelSequential General Search paradigm is presented that unifies the various parallel models and is used to extend the GA toolkit into a parallel GA toolkit for a parallel system based on Transputers. The parallel GA models are applied to problems from both of the case studies considered in this thesis. A comparison between the various parallel GA models concludes this chapter. The thesis finishes with a summary of a number of conclusions drawn from this research together with some suggestions for how this work may be continued in the future.

No description available.

ITC/USA 2010 Conference Proceedings / The Forty-Sixth Annual International Telemetering Conference and Technical Exhibition / October 25-28, 2010 / Town and Country Resort & Convention Center, San Diego, California / There is growing concern that the U.S. military can no longer meet its domestic and international spectrum needs. Demand for this resource is growing at an exponential pace, both within the Department of Defense (DoD) and in the commercial sector (partly due to rapid growth in broadband wireless electronics). A microcosm of these challenges is evident in flight test operations, where there is a growing need for advanced spectrum assignment, frequency deconfliction, and scheduling optimization decision support capabilities. This paper describes research aimed at investigating how to optimize frequency scheduling, dynamic assignment, and real-time metrics adjustment to promote assured access to the electronic spectrum, including emerging technology developments to support that need.

ITC/USA 2011 Conference Proceedings / The Forty-Seventh Annual International Telemetering Conference and Technical Exhibition / October 24-27, 2011 / Bally's Las Vegas, Las Vegas, Nevada / Current real-time data communications links supporting Major Range and Test Facility Base (MRTFB) operations are one-way, dedicated links based on the IRIG 106 standard. One of the goals of the iNET program is to provide for shared, two-way networked communications links enabling more flexible operation and more efficient use of spectrum. Central to this goal is the provision for a Spectrum Assignment Manager (SAM) as referred to in the iNET architecture. The SAM element of the Resource Management Facility (RMF) works in concert with the TmNS Network Manager to support dynamic frequency assignment and real-time metrics adjustment. This paper describes the potential role, key functions, and technology elements needed to support this important function.

<p>This Master’s Thesis deals with a special problem that may be of importance when planning a frequency hopping mobile communication network. In normal cases the Frequency Assignment Problem is solved, in order to plan the use of frequencies in a network. The special case discussed in this thesis occurs when the network operator requires that the frequencies must be arranged into groups. In this case the Frequency Assignment Problem must be solved with respect to the groups, i.e. a Group assignment Problem. </p><p>The thesis constitutes the final part of the Master of Science in Communication and Transport Systems Engineering education, at Linköping University, Campus Norrköping. The Group Arrangement Problem was presented by ComOpt, a company that has specialized in solving the Frequency Assignment Problem for network operators. </p><p>This thesis does not deal with solutions for the Frequency Assignment Problem, with respect to the groups. The main issue in the thesis is to construct a computer based algorithm that solves the Group Arrangement Problem, i.e. creating the groups. The goal is to construct an algorithm that creates groups which imply a better solution for the Frequency Assignment Problem than manually created groups. </p><p>Two algorithms are presented and tested on two cases. Their respective results for both cases are compared with the results from a manual grouping. The two computer based algorithms creates better groups than the manual grouping strategy, according to an artificial quality measure. As of spring 2003 a variant of one of the presented algorithms was implemented in ComOpt’s product for solving the Frequency Assignment Problem.</p>

This Master’s Thesis deals with a special problem that may be of importance when planning a frequency hopping mobile communication network. In normal cases the Frequency Assignment Problem is solved, in order to plan the use of frequencies in a network. The special case discussed in this thesis occurs when the network operator requires that the frequencies must be arranged into groups. In this case the Frequency Assignment Problem must be solved with respect to the groups, i.e. a Group assignment Problem. The thesis constitutes the final part of the Master of Science in Communication and Transport Systems Engineering education, at Linköping University, Campus Norrköping. The Group Arrangement Problem was presented by ComOpt, a company that has specialized in solving the Frequency Assignment Problem for network operators. This thesis does not deal with solutions for the Frequency Assignment Problem, with respect to the groups. The main issue in the thesis is to construct a computer based algorithm that solves the Group Arrangement Problem, i.e. creating the groups. The goal is to construct an algorithm that creates groups which imply a better solution for the Frequency Assignment Problem than manually created groups. Two algorithms are presented and tested on two cases. Their respective results for both cases are compared with the results from a manual grouping. The two computer based algorithms creates better groups than the manual grouping strategy, according to an artificial quality measure. As of spring 2003 a variant of one of the presented algorithms was implemented in ComOpt’s product for solving the Frequency Assignment Problem.

This thesis has focused on an aircraft schedule and network design problem that involves multiple types of aircraft and flight service. First, this thesis expands a business model for integrating on-demand flight services with the traditional scheduled flight services. Then, this thesis proposes a three-step approach to the design of aircraft schedules and networks from scratch. After developing models in the three steps and creating large-scale instances of these models, this dissertation develops iterative algorithms and subproblem approaches to solving these instances, and it presents computational results of these large-scale instances. To validate the models and solution algorithms developed, this thesis compares the daily flight schedules that it designed with the schedules of the existing airlines. In addition, it discusses the implication of using new aircraft in the future flight schedules. Finally, future research in three areas--model, computational method, and simulation for validation--is proposed.

The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

L’affectation de fr´equences (AFP) consiste `a attribuer des fr´equences radio aux liens de communications d’un r´eseauen respectant un spectre de fr´equences donn´e et des contraintes d’interf´erence ´electromagn´etique sur les liens. Vu lalimitation des ressources spectrales pour chaque application, les ressources en fr´equences sont souvent insuffisantespour d´eployer un r´eseau sans interf´erence. Dans ce cas, le r´eseau est surcontraint et le probl`eme est irr´ealisable.R´esoudre le probl`eme consiste alors `a identifier les zones surcontraintes pour en revoir la conception.Le travail que nous pr´esentons concerne la recherche d’une de ces zones surcontraintes avec une approche algo-rithmique bas´ee sur la mod´elisation du probl`eme par un CSP. Le probl`eme de l’affectation de fr´equences doit doncˆetre mod´elis´e comme un probl`eme de satisfaction de contraintes (CSP) qui est repr´esent´e par un tripl´e : un ensemblede variables (les liens radio), un ensemble de contraintes (les interf´erences ´electromagn´etiques), et un ensemble dedomaines (les fr´equences admises).Sous forme de CSP, une zone perturb´ee peut ˆetre consid´er´ee comme un sous-ensemble irr´ealisable irr´eductible duprobl`eme (IIS pour Irreductible Infeasible Subset). Un IIS est un sous probl`eme de taille minimale qui est irr´ealisable,c’est-`a-dire que tous les sous-ensembles d’un IIS sont r´ealisables. L’identification d’un IIS dans un CSP se rapporte `a deux r´esultats g´en´eraux int´eressants. Premi`erement, en localisant un IIS on peut plus facilement prouver l’irr´ealisabilit´ed’un probl`eme donn´e car l’irr´ealisabilit´e d’un IIS, qui est suppos´e ˆetre petit par rapport au probl`eme complet, est plusrapidement calculable que sur le probl`eme entier. Deuxi`emement, on peut localiser la raison de l’irr´ealisabilit´e; dansce cas, sur un probl`eme r´eel, le d´ecideur peut proposer des solutions pour relˆacher des contraintes de l’IIS, et peut-ˆetre aboutir `a une solution r´ealisable pour son probl`eme. La recherche d’IIS consiste donc `a r´esoudre un probl`emefondamental qui fait partie des outils de prise de d´ecision.Ce travail propose des algorithmes pour identifier un IIS dans un CSP incoh´erent. Ces algorithmes ont ´et´e test´essur des instances connues du probl`eme de l’affectation des fr´equences et du probl`eme de k-coloration de graphe. Lesr´esultats ont montr´es d’une grande am´elioration sur des instances du probl`eme de l’affectation des fr´equences parrapport aux m´ethodes connues. / The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

Les applications réelles liées aux problèmes de satisfaction partielle de contraintes (PCSP : Partial Constraints Satisfaction Problem) sont de plus en plus nombreuses, ce qui justifie l’intérêt croissant des chercheurs pour cette classe de problèmes. La résolution d’un PCSP revient à affecter des valeurs à toutes ses variables tout en maximisant (ou minimisant) une fonction objectif prédéfinie. Ces problèmes sont NP-difficiles, par conséquent il n’existe aucune approche aussi bien exacte qu’heuristique efficace sur les grandes instances. Pour résoudre efficacement les instances difficiles, une multitude de solutions sont proposées, allant de l’hybridation à l’apprentissage en passant par la décomposition. Dans notre travail, nous nous intéressons à cette dernière proposition, qui consiste à fractionner le problème PCSP en plusieurs sous-problèmes PCSP de tailles raisonnables, puis proposer des algorithmes de résolution pour les problèmes décomposés. Cette approche a pour but de bénéficier de la structure du problème afin d’accélérer sa résolution tout en garantissant des solutions optimales ou sous-optimales. Deux grand axes sont explorés : les approches basées sur la décomposition et celles guidées par la décomposition. Les approches basées sur la décomposition consistent à résoudre séparément les parties difficiles du problème décomposé, puis combiner les solutions partielles obtenues en vue d’atteindre une solution globale du problème d’origine. Les approches guidées par la décomposition consistent à développer des métaheuristiques qui tiennent compte de la structure du problème décomposé. Les algorithmes proposés sont testés et validés sur des instances réelles des problèmes PSCP, comme le problème d’affectation de fréquences et le problème de coloration de graphes / The wide range of potential applications concerned by the resolution of Partial Constraints Satisfaction Problems (PCSP) justifies the growing interest of scientists in this class of problems. Solving a PCSP means searching for values to assign to the decision variables in order to maximize (or minimize) a predefined objective function. These problems are NP-hard, so there isn’t an exact approach nor an efficient heuristic able to provide the optimal solution for large instances. In order to solve effectively the difficult instances, numerous approaches based on hybridization, learning or decomposition are proposed. In the present work, we focus on the latter proposal, which consists in splitting the PCSP into several smaller size PCSPs and we propose some methods to solve the decomposed problem. Two wide axes are explored : the resolution based on the decomposition and the one guided by decomposition. The former solves separately the difficult parts of the decomposed problem (cuts or clusters) and then combines partial solutions obtained in order to achieve a global solution for the original problem. The latter aims at benefiting from the structure of the problem to be decomposed in order to accelerate its resolution while ensuring optimal or near optimal solutions. All the proposed algorithms are tested and validated on the well-known benchmarks of PCSP problems such as Frequency Assignment Problem (FAP) and graph coloring problem