Publishing Service

Polishing & Checking

Journal of Zhejiang University SCIENCE C

ISSN 1869-1951(Print), 1869-196x(Online), Monthly

A membrane-inspired algorithm with a memory mechanism for knapsack problems

Abstract: Membrane algorithms are a class of distributed and parallel algorithms inspired by the structure and behavior of living cells. Many attractive features of living cells have already been abstracted as operators to improve the performance of algorithms. In this work, inspired by the function of biological neuron cells storing information, we consider a memory mechanism by introducing memory modules into a membrane algorithm. The framework of the algorithm consists of two kinds of modules (computation modules and memory modules), both of which are arranged in a ring neighborhood topology. They can store and process information, and exchange information with each other. We test our method on a knapsack problem to demonstrate its feasibility and effectiveness. During the process of approaching the optimum solution, feasible solutions are evolved by rewriting rules in each module, and the information transfers according to directions defined by communication rules. Simulation results showed that the performance of membrane algorithms with memory cells is superior to that of algorithms without memory cells for solving a knapsack problem. Furthermore, the memory mechanism can prevent premature convergence and increase the possibility of finding a global solution.

Key words: Membrane algorithm, Memory mechanism, Knapsack problem


Share this article to: More

Go to Contents

References:

<Show All>

Open peer comments: Debate/Discuss/Question/Opinion

<1>

Please provide your name, email address and a comment





DOI:

10.1631/jzus.C1300005

CLC number:

TP301

Download Full Text:

Click Here

Downloaded:

3065

Download summary:

<Click Here> 

Downloaded:

2481

Clicked:

8109

Cited:

7

On-line Access:

2024-08-27

Received:

2023-10-17

Revision Accepted:

2024-05-08

Crosschecked:

2013-07-12

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952276; Fax: +86-571-87952331; E-mail: jzus@zju.edu.cn
Copyright © 2000~ Journal of Zhejiang University-SCIENCE