Chaotic Walk in Simulated Annealing Search Space for Task Allocation in a Multiprocessing System

Chaotic Walk in Simulated Annealing Search Space for Task Allocation in a Multiprocessing System

Ken Ferens (Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, Canada), Darcy Cook (JCA Electronics, Winnipeg, Canada) and Witold Kinsner (Department of Electrical and Computer Engineering, University of Manitoba, Winnipeg, Canada)
DOI: 10.4018/ijcini.2013070104
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

This paper proposes the application of chaos in large search space problems, and suggests that this represents the next evolutionary step in the development of adaptive and intelligent systems towards cognitive machines and systems. Three different versions of chaotic simulated annealing (XSA) were applied to combinatorial optimization problems in multiprocessor task allocation. Chaotic walks in the solution space were taken to search for the global optimum or “good enough” task-to-processor allocation solutions. Chaotic variables were generated to set the number of perturbations made in each iteration of a XSA algorithm. In addition, parameters of a chaotic variable generator were adjusted to create different chaotic distributions with which to search the solution space. The results show that the convergence rate of the XSA algorithm is faster than simulated annealing when the solutions are far apart in the solution space. In particular, the XSA algorithms found simulated annealing’s best result on average about 4 times faster than simulated annealing.
Article Preview

1. Introduction

Many attempts are being made to evolve adaptive and intelligent systems to cognitive machines and systems (e.g., Kinsner, 2007(Kinsner, 2007); Kinsner, 2009(Kinsner, 2009); Hollnagel & Woods, 2005) such as cognitive radio (e.g., Haykin, 2005 ; Biglieri, Goldsmith, Greenstein, Mandayam, & Poor, 2013), cognitive radar (Haykin, 2006), cognitive wireless networks (e.g., Hossain & Bhargava, 2010; Marshall, 2013), cognitive control (Haykin, Fatemi, Setoodeh, & Xue, 2012), cognitive robots (Wang, Zhang, & Kinsner, 2010), cognitive security (Kinsner, 2012), cognitive signal processing (e.g., (Kinsner & Zhang, 2010)), cognitive computing (e.g., Wang, Kinsner, & Zhang, 2009; Wang, Zhang, & Kinsner, 2010), cognitive dynamic systems (Haykin, 2012). Such developments have been facilitated by advances in cognitive science (e.g., Posner, 1989; Ward, 2002; Fuster, Cortex, & Mind, 2005), cognitive informatics (e.g., Wang, 2002; Wang, 2002; Wang, Zhang, & Kinsner, 2010), information theory (e.g., (Downarowicz, 2011)), structural computing (e.g., (Bishop, 1995)), fuzzy, rough and granular computing (e.g., Pedrycz & Gomide, 1998; Friedman & Kandel, 1999; Pawlak, 1991; Pedrycz, 2001), perceptual computing (e.g., (Skowron & Wasilewski, 2010)), multi-scale signal processing (e.g., (Mallat, 1988)), poly-scale signal processing (e.g., Kinsner, 2013; Kinsner, 2007; Kinsner, Cheung, Pear, & Martin, 2006; Peitgen, Jurgens, & Saupe, 2004; Strogatz, 1994) and intelligent signal processing (e.g., Haykin & Kosko, 2001; Haykin, Principe, Sejnowski, & McWhirter, 2006; Gadhok & Kinsner, 2008).

Adaptive and intelligent systems have emerged as a viable approach to reducing the computation time of searching large spaces to find solutions to difficult problems. In many cases the optimal solution to a problem with large search space cannot be determined in polynomial time, because any known non-adaptive and non-intelligent algorithm applied to the problem would take a very long time to complete a search of the entire space. For instance, the problem of allocating a set of tasks N with dependencies to a set of heterogeneous processors M in a multiprocessor system is a very difficult problem, especially for large numbers of tasks and processors. The worst case approach, an exhaustive search, would require evaluating and comparing every possible combination of task to processor allocation to determine the “best” solution, which, for a large search space and today’s computing technology, may take a number of computation-years more than the number of particles in this universe. Thus, adaptive and intelligent approaches arose to find solutions to difficult problems.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 11: 4 Issues (2017): 3 Released, 1 Forthcoming
Volume 10: 4 Issues (2016)
Volume 9: 4 Issues (2015)
Volume 8: 4 Issues (2014)
Volume 7: 4 Issues (2013)
Volume 6: 4 Issues (2012)
Volume 5: 4 Issues (2011)
Volume 4: 4 Issues (2010)
Volume 3: 4 Issues (2009)
Volume 2: 4 Issues (2008)
Volume 1: 4 Issues (2007)
View Complete Journal Contents Listing