Massey Documents by Type
Permanent URI for this communityhttps://mro.massey.ac.nz/handle/10179/294
Browse
4 results
Search Results
Item Evolving and co-evolving meta-level reasoning strategies for multi-agent collaboration : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Albany, New Zealand(Massey University, 2024) Alshehri, Mona Abdulrahman MThis research presents a novel hybrid evolutionary algorithm for generating meta-level reasoning strategies through computational graphs to solve multi-agent planning and collaboration problems in dynamic environments using only a sparse training set. We enhanced Genetic Network Programming (GNP) by reducing its reliance on randomness, using conflict extractions and optimal search in computational mechanisms to explore nodes more systematically. We incorporated three algorithms into the GNP core. Firstly, we used private conflict kernels to extract conflict-generating structures from graph solutions, which enhances selection, crossover, and mutation operations. Secondly, we enhanced the GNP algorithm by incorporating optimal search and merged Conflict Directed A* with GNP to reduce the search branching factor. We call our novel algorithm Conflict-Directed A* with Genetic Network Programming (CDA*-GNP), which identifies the most effective combination of processing nodes within the graph solution. Additionally, we investigated the use of a chromosome structure with multiple subprograms of varying sizes that the algorithm automatically adjusts. Thirdly, we applied Conflict-Directed A* to a genetically co-evolving heterogeneous cooperative system. A set of agents with diversified computational node composition is evolved to identify the best collection of team members and to efficiently prevent conflicting members from being in the same team. Also, we incorporated methods to enhance the population diversity in each proposed algorithm. We tested the proposed algorithms using four cooperative multi-agent testbeds, including the prey and predator problem and the original tile world problem. More complex multi-agent and multi-task benchmarking testbeds were also introduced for further evaluation. As compared to existing variants of GNP, experimental results show that our algorithm has smoother and more stable fitness improvements across generations. Using the popular tile world problem as a benchmarking testbed, CDA*-GNP achieved better performance results than the best existing variant of GNP for solving the problem. Our algorithm returned 100% accuracy on the test set compared to only 83% reported in the literature. Moreover, CDA*-GNP is 78% faster in terms of the average number of generations and 74% faster in terms of the average number of fitness evaluations. In general, our findings suggest that a hybrid algorithm that balances the utilization of Genetic Network Programming and Optimal strategies leads to the evolution of high-quality solutions faster.Item Genetic network programming with reinforcement learning and optimal search component : a thesis presented in partial fulfilment of the requirements for the degree of Master of Science in Computer Sciences at Massey University, Auckland, New Zealand(Massey University, 2019) Alshehri, Mona Abdulrahman MThis thesis presents ways of improving the genetic composition, structure and learning strategies for a graph-based evolutionary algorithm, called Genetic Networking Programming with Reinforcement Learning (GNP-RL), particularly when working with multi-agent and dynamic environments. GNP-RL is an improvement over Genetic Programming, allowing for the concise representation of solutions in terms of a networked graph structure and uses RL to further refine the graph solutions. This work has improved GNP-RL by combining three new techniques: Firstly, it has added a reward and punishment scheme as part of its learning strategy that supports constraint conformance, allowing for a more adaptive training of the agent, so that it can learn how to avoid unwanted situations more effectively. Secondly, an optimal search algorithm has been combined in the GNP-RL core to get an accurate analysis of the exploratory environment. Thirdly, a task prioritization technique has been added to the agent’s learning by giving promotional rewards, so they are trained on how to take priority into account when performing tasks. In this thesis, we applied the improved algorithm to the Tile World benchmarking testbed, which is considered as one of the standard complex problems in this domain, having only a sparse training set. Our experiment results show that the proposed algorithm is superior than the best existing variant of the GNP-RL algorithm [1]. We have achieved 86.66% test accuracy on the standard benchmarking dataset [2]. In addition, we have created another benchmarking dataset, similar in complexity to the one proposed in [1], to test the proposed algorithms further, where it achieved a test accuracy of 96.66%; that is 33.66% more accurate.Item Computational complexity of elitist population-based evolutionary algorithms : a thesis presented in partial fulfilment of the requirements for the degree of Doctor of Philosophy in Computer Science at Massey University, Palmerston North, New Zealand(Massey University, 2012) Ter-Sarkisov, AramEvolutionary Algorithms (EAs) are a modern heuristic algorithm that have proven efficiency on a large number of real-life problems. Despite the rich history of applications understanding of both how and why EAs work is lagging far behind. This is especially true for one of the main components of EAs, that is hypothesized by many to underlie their efficiency: population. The first problem considered in this thesis is the introduction of a recombination operator, K-Bit-Swap (KBS) and its comparison to mainstream operators, such as mutation and different types of crossover. A vast amount of statistical evidence is presented that shows that EAs using KBS outperform other algorithms on a whole range of problems. Two problems are selected for a deep theoretical analysis: OneMax and Royal Roads. The main problem of modeling EAs that use both population and a pool of parents is the complexity of the structures that arise from the process of evolution. In most cases either one type of species is considered or certain simple assumptions are made about fitness of the species. The main contribution of this thesis is the development of a new approach to modeling of EAs that is based on approximating the structure of the population and the evolution of subsets thereof. This approach lies at the core of the new tool presented here, the Elitism Levels Traverse Mechanism that was used to derive upper bounds on the runtime of EAs. In addition, lower bounds were found using simpler assumptions of the underlying distribution of species in the population.The second important result of the approach is the derivation of limiting distributions of a subset of the population, a problem well-known in areas such as epidemiology. To the best of the author's knowledge, no such findings have been published in the EA community so far.Item Point trajectory planning of flexible redundant robot manipulators using genetic algorithms(Cambridge, 2002) Yue, Shigang; Henrich, Dominik; Xu, W. L.; Tso, S. K.The paper focuses on the problem of point-to-point trajectory planning for flexible redundant robot manipulators (FRM) in joint space. Compared with irredundant flexible manipulators, a FRM possesses additional possibilities during point-to-point trajectory planning due to its kinematics redundancy. A trajectory planning method to minimize vibration and/or executing time of a point-to-point motion is presented for FRMs based on Genetic Algorithms (GAs). Kinematics redundancy is integrated into the presented method as planning variables. Quadrinomial and quintic polynomial are used to describe the segments that connect the initial, intermediate, and final points in joint space. The trajectory planning of FRM is formulated as a problem of optimization with constraints. A planar FRM with three flexible links is used in simulation. Case studies show that the method is applicable.