Particle swarm optimization for two-connected networks with bounded rings

The Two-Connected Network with Bounded Ring (2CNBR) problem is a network design problem addressing the connection of servers to create a survivable network with limited redirections in the event of failures. Particle Swarm Optimization (PSO) is a stochastic population-based optimization technique modeled on the social behaviour of flocking birds or schooling fish. This thesis applies PSO to the 2CNBR problem. As PSO is originally designed to handle a continuous solution space, modification of the algorithm was necessary in order to adapt it for such a highly constrained discrete combinatorial optimization problem. Presented are an indirect transcription scheme for applying PSO to such discrete optimization problems and an oscillating mechanism for averting stagnation.

A Study of Ordered Gene Problems Featuring DNA Error Correction and DNA Fragment Assembly with a Variety of Heuristics, Genetic Algorithm Variations, and Dynamic Representations

Ordered gene problems are a very common classification of optimization problems. Because of their popularity countless algorithms have been developed in an attempt to find high quality solutions to the problems. It is also common to see many different types of problems reduced to ordered gene style problems as there are many popular heuristics and metaheuristics for them due to their popularity. Multiple ordered gene problems are studied, namely, the travelling salesman problem, bin packing problem, and graph colouring problem. In addition, two bioinformatics problems not traditionally seen as ordered gene problems are studied: DNA error correction and DNA fragment assembly. These problems are studied with multiple variations and combinations of heuristics and metaheuristics with two distinct types or representations. The majority of the algorithms are built around the Recentering- Restarting Genetic Algorithm. The algorithm variations were successful on all problems studied, and particularly for the two bioinformatics problems. For DNA Error Correction multiple cases were found with 100% of the codes being corrected. The algorithm variations were also able to beat all other state-of-the-art DNA Fragment Assemblers on 13 out of 16 benchmark problem instances.

Characterizing Dynamic Optimization Benchmarks for the Comparison of Multi-Modal Tracking Algorithms

Population-based metaheuristics, such as particle swarm optimization (PSO), have been employed to solve many real-world optimization problems. Although it is of- ten sufficient to find a single solution to these problems, there does exist those cases where identifying multiple, diverse solutions can be beneficial or even required. Some of these problems are further complicated by a change in their objective function over time. This type of optimization is referred to as dynamic, multi-modal optimization. Algorithms which exploit multiple optima in a search space are identified as niching algorithms. Although numerous dynamic, niching algorithms have been developed, their performance is often measured solely on their ability to find a single, global optimum. Furthermore, the comparisons often use synthetic benchmarks whose landscape characteristics are generally limited and unknown. This thesis provides a landscape analysis of the dynamic benchmark functions commonly developed for multi-modal optimization. The benchmark analysis results reveal that the mechanisms responsible for dynamism in the current dynamic bench- marks do not significantly affect landscape features, thus suggesting a lack of representation for problems whose landscape features vary over time. This analysis is used in a comparison of current niching algorithms to identify the effects that specific landscape features have on niching performance. Two performance metrics are proposed to measure both the scalability and accuracy of the niching algorithms. The algorithm comparison results demonstrate the algorithms best suited for a variety of dynamic environments. This comparison also examines each of the algorithms in terms of their niching behaviours and analyzing the range and trade-off between scalability and accuracy when tuning the algorithms respective parameters. These results contribute to the understanding of current niching techniques as well as the problem features that ultimately dictate their success.

A Scalability Study and New Algorithms for Large-Scale Many-Objective Optimization

Many real-world optimization problems contain multiple (often conflicting) goals to be optimized concurrently, commonly referred to as multi-objective problems (MOPs). Over the past few decades, a plethora of multi-objective algorithms have been proposed, often tested on MOPs possessing two or three objectives. Unfortunately, when tasked with solving MOPs with four or more objectives, referred to as many-objective problems (MaOPs), a large majority of optimizers experience significant performance degradation. The downfall of these optimizers is that simultaneously maintaining a well-spread set of solutions along with appropriate selection pressure to converge becomes difficult as the number of objectives increase. This difficulty is further compounded for large-scale MaOPs, i.e., MaOPs possessing large amounts of decision variables. In this thesis, we explore the challenges of many-objective optimization and propose three new promising algorithms designed to efficiently solve MaOPs. Experimental results demonstrate the proposed optimizers to perform very well, often outperforming state-of-the-art many-objective algorithms.

The Salmon Algorithm - A New Population Based Search Metaheuristic

This thesis introduces the Salmon Algorithm, a search meta-heuristic which can be used for a variety of combinatorial optimization problems. This algorithm is loosely based on the path finding behaviour of salmon swimming upstream to spawn. There are a number of tunable parameters in the algorithm, so experiments were conducted to find the optimum parameter settings for different search spaces. The algorithm was tested on one instance of the Traveling Salesman Problem and found to have superior performance to an Ant Colony Algorithm and a Genetic Algorithm. It was then tested on three coding theory problems - optimal edit codes, optimal Hamming distance codes, and optimal covering codes. The algorithm produced improvements on the best known values for five of six of the test cases using edit codes. It matched the best known results on four out of seven of the Hamming codes as well as three out of three of the covering codes. The results suggest the Salmon Algorithm is competitive with established guided random search techniques, and may be superior in some search spaces.

An examination of grade three mathematics textbooks for problem solving strategies

Three grade three mathematics textbooks were selected arbitrarily (every other) from a total of six currently used in the schools of Ontario. These textbooks were examined through content analysis in order to determine the extent (i. e., the frequency of occurrence) to which problem solving strategies appear in the problems and exercises of grade three mathematics textbooks, and how well they carry through the Ministry's educational goals set out in The Formative Years. Based on Polya's heuristic model, a checklist was developed by the researcher. The checklist had two main categories, textbook problems and process problems and a finer classification according to the difficulty level of a textbook problem; also six commonly used problem solving strategies for the analysis of a process problem. Topics to be analyzed were selected from the subject guideline The Formative Years, and the same topics were selected from each textbook. Frequencies of analyzed problems and exercises were compiled and tabulated textbook by textbook and topic by topic. In making comparisons, simple frequency count and percentage were used in the absence of any known criteria available for judging highor low frequency. Each textbook was coded by three coders trained to use the checklist. The results of analysis showed that while there were large numbers of exercises in each textbook, not very many were framed as problems according to Polya' s model and that process problems form a small fraction of the number of analyzed problems and exercises. There was no pattern observed as to the systematic placement of problems in the textbooks.

Decoding algorithms using side-effect machines

Bioinformatics applies computers to problems in molecular biology. Previous research has not addressed edit metric decoders. Decoders for quaternary edit metric codes are finding use in bioinformatics problems with applications to DNA. By using side effect machines we hope to be able to provide efficient decoding algorithms for this open problem. Two ideas for decoding algorithms are presented and examined. Both decoders use Side Effect Machines(SEMs) which are generalizations of finite state automata. Single Classifier Machines(SCMs) use a single side effect machine to classify all words within a code. Locking Side Effect Machines(LSEMs) use multiple side effect machines to create a tree structure of subclassification. The goal is to examine these techniques and provide new decoders for existing codes. Presented are ideas for best practices for the creation of these two types of new edit metric decoders.

The expression and development of teachers' capacities within two learning communities : a participant-observer case study

The learning community model has been an integral component of teacher development in Ontarian schools and beyond. This research was conducted to understand how teachers' personal capacity and professional, interpersonal, and organizational competencies are developed and expressed within this context. Nineteen elementary teachers and administrators participated in the study from November through January 2007. A qualitative case study methodology was used to investigate the role ofteachers' capacities and competencies in learning communities. Combined data sources from semistructured interviews, research journals, and document review were used to gather data about teachers' capacities and competencies. The study included 3 phases of analysis. In the final phase the analysis provided 3 qualities of the teachers at Jude and Mountain Schools (pseudonyms): identification as professionals, investment in others, and institutional affiliation that may explain how they differed from other educators. The data revealed these three themes, which provided an understanding of educators at Jude and Mountain Schools as dedicated professionals pushing practices to contribute to school life and address student learning needs, and as teachers who reflected on practices to continue expanding their skills. Teachers were heavily invested in creating a caring culture and in students' and team members' learning. Educators actively participated in solving problems and coplanning throughout the school levels and beyond, assumed collective responsibility for all pupils, and focused on generating school-wide consistent practices. These qualities and action patterns revealed teachers who invested time and effort in their colleagues, who committed to develop as professionals, and who affiliated closely with every aspect of school living.