| Solving multiconstraint assignment problems using learning automata. | |
| | |
MedLine Citation:
|
PMID: 19884057 Owner: NLM Status: PubMed-not-MEDLINE |
Abstract/OtherAbstract:
|
This paper considers the NP-hard problem of object assignment with respect to multiple constraints: assigning a set of elements (or objects) into mutually exclusive classes (or groups), where the elements which are "similar" to each other are hopefully located in the same class. The literature reports solutions in which the similarity constraint consists of a single index that is inappropriate for the type of multiconstraint problems considered here and where the constraints could simultaneously be contradictory. This feature, where we permit possibly contradictory constraints, distinguishes this paper from the state of the art. Indeed, we are aware of no learning automata (or other heuristic) solutions which solve this problem in its most general setting. Such a scenario is illustrated with the static mapping problem, which consists of distributing the processes of a parallel application onto a set of computing nodes. This is a classical and yet very important problem within the areas of parallel computing, grid computing, and cloud computing. We have developed four learning-automata (LA)-based algorithms to solve this problem: First, a fixed-structure stochastic automata algorithm is presented, where the processes try to form pairs to go onto the same node. This algorithm solves the problem, although it requires some centralized coordination. As it is desirable to avoid centralized control, we subsequently present three different variable-structure stochastic automata (VSSA) algorithms, which have superior partitioning properties in certain settings, although they forfeit some of the scalability features of the fixed-structure algorithm. All three VSSA algorithms model the processes as automata having first the hosting nodes as possible actions; second, the processes as possible actions; and, third, attempting to estimate the process communication digraph prior to probabilistically mapping the processes. This paper, which, we believe, comprehensively reports the pioneering LA solutions to this problem, unequivocally demonstrates that LA can play an important role in solving complex combinatorial and integer optimization problems. |
| | |
Authors:
|
Geir Horn; B John Oommen |
Related Documents
:
|
3797557 - Keats's oral imagination: "'tis not through envy". 17202267 - Searching with iterated maps. 1316537 - Aids and sle: a reverse process of the same disease. 9063617 - On assumptions of, relations between, and evaluations of some process dissociation meas... 1810247 - Isolation and characterization of a lethal phospholipase a2 (nn-ivb1-pla2) from the ind... 21819847 - The development and application of a proxy measure of alcohol-related traffic crashes f... |
Publication Detail:
|
Type: Journal Article; Research Support, Non-U.S. Gov't |
Journal Detail:
|
Title: IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society Volume: 40 ISSN: 1941-0492 ISO Abbreviation: IEEE Trans Syst Man Cybern B Cybern Publication Date: 2010 Feb |
Date Detail:
|
Created Date: 2009-11-03 Completed Date: 2010-01-14 Revised Date: - |
Medline Journal Info:
|
Nlm Unique ID: 9890044 Medline TA: IEEE Trans Syst Man Cybern B Cybern Country: United States |
Other Details:
|
Languages: eng Pagination: 6-18 Citation Subset: - |
Affiliation:
|
Simula Research Laboratory, 1325 Lysaker, Norway. Geir.Horn@sintef.no |
Export Citation:
|
APA/MLA Format Download EndNote Download BibTex |
| MeSH Terms | |
Descriptor/Qualifier:
|
|
From MEDLINE®/PubMed®, a database of the U.S. National Library of Medicine
Previous Document: Translation and French cultural adaptation of a decision making tool for patients orientation after ...
Next Document: A team of continuous-action learning automata for noise-tolerant learning of half-spaces.