Thesis Format

Monograph

A Modified Hopfield Network for the K-Median Problem

Cody Rossiter, The University of Western OntarioFollow

Degree

Master of Science

Program

Computer Science

Supervisor

Solis-Oba, Roberto

Abstract

The k-median problem is a clustering problem where given n locations one wants to select k locations such that the total distance between every non-selected location and its nearest selected location is minimized. The problem has applications in several fields, including network design, resource allocation, and data mining.

There is currently limited research on applying neural networks to combinatorial optimization problems and we contribute by presenting a modified Hopfield network for the k-median problem. Hopfield networks are a type of neural network that can be applied to combinatorial optimization problems but often run slowly and produce poor solutions.

Our modifications address these speed and solution quality issues. We test our approach by comparing it with Haralampiev’s competition-based neural network and the local search algorithm of Arya, Garg, Khandekar, Meyerson, Munagala, and Pandit. Our network produces competitive results while running significantly faster on larger (n ≥ 300) problems. Furthermore, our network scales well and produces solutions for problems where n = 13509.

Summary for Lay Audience

Combinatorial optimization problems are an important field of computer science. Here we are given a group of objects and we want to select the best subgroup of objects in order to solve a problem. We focus on the k-median problem where we are given several locations and we want to select k of them. We call these selected locations facilities and our goal is to select facilities such that the total distance from all locations to their nearest facility is minimized.

A practical application of the k-median problem is placing schools so that student travel time is minimized. Unfortunately this problem is difficult to solve and it is not known if there is a fast way to always produce the best solution. Instead, we can develop an approach that will run quickly and produce a good solution instead of the best solution.

We use a type of artificial neural network called a Hopfield network to produce solutions for the k-median problem. Artificial neural networks solve problems by emulating how neurons in the brain function. We do this by creating simple artificial neurons and connecting them together so that their output can be used to solve problems. In Hopfield networks, each neuron has a value that can be 0 or 1 and changes over time based on the other values in the network. Once the neuron values stop changing, we use the neuron values to determine which facilities to select.

However, Hopfield networks often run slowly and produce poor solutions. To address this we make several modifications to the network. We demonstrate the effectiveness of our modified Hopfield network by using it to solve several k-median problems. We also compare the performance of our modified Hopfield network with two other approaches and we find that our network produces competitive solutions. Furthermore, our network scales well as we were able to solve problems that were too large for the other two approaches solve.

Recommended Citation

Rossiter, Cody, "A Modified Hopfield Network for the K-Median Problem" (2023). Electronic Thesis and Dissertation Repository. 9152.
https://ir.lib.uwo.ca/etd/9152