fairfolio
Saved Projects

Parallel Max-Min Ant System for Solving Combinatorial Constraint-satisfaction Problems

ISEF · 2020 Systems Software

Vulakh, David · Paul Laurence Dunbar High School

Is this your project?

Overview

Many mathematical and practical problems, such as Sudoku, timetabling, and resource distribution, require elements of a set to be arranged in a way that satisfies specific conditions. Such tasks, called constraint-satisfaction problems (CSPs), include NP-complete instances, so there is no known polynomial-time algorithm to solve the general-case CSP. In order to reduce the time required to solve large CSP instances, an Ant Colony Optimization (ACO) algorithm called the Max-Min Ant System (MMAS) was adapted for combinatorial CSPs, parallelized, and augmented with new heuristics. The resulting MMAS framework was tested for a specific CSP instance (the Costas-array problem, which remains an open problem in mathematics for some sizes). The effectiveness of the MMAS framework was assessed by computing its efficiency with respect to number of processors utilized and comparing its runtimes with and without the new heuristics. By both measurements, the parallel MMAS framework proved to be an effective tool for solving CSPs. The MMAS framework maintained efficient processor utilization (E=1) for problem sizes M=13 and exhibited lower runtimes when using the new heuristics. Higher levels of parallelization can be achieved in the future by investigating distributed versions of MMAS that can pool the computational resources of multiple machines.

Working on something like this? See what's been done and what's still open.

Competition history

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Report a problem

Source: Regeneron International Science and Engineering Fair

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google