International Journal of Computational Intelligence Research (IJCIR)
Volume 2, Issue 4
Regular Papers in Press
A Hybrid Evolutionary
Approach to Maximum Weight Clique Problem
Alok Singh and Ashok Kumar Gupta
J. K. Institute of Applied Physics and Technology,
Faculty of Science, University of Allahabad,
Allahabad – 211002, India
Abstract: In this paper, we propose a hybrid evolutionary approach combining
steady-state genetic algorithm and a greedy heuristic for the maximum weight
clique problem. The genetic algorithm generates cliques that are then extended
into maximum weight clique by the heuristic. Tests on a variety of benchmark
problem instances demonstrate the effectiveness of our approach.
Hierarchical Two-Population Genetic Algorithm
Jarno Martikainen and
Seppo J. Ovaska
Helsinki University of Technology, Institute of Intelligent Power Electronics
P. O. Box 3000, 02015 HUT, Finland
Abstract: This paper proposes a new hierarchical two-population genetic
algorithm (2PGA). The 2PGA scheme constitutes of two differently sized
populations containing individuals of similar fitness or cost function values.
The smaller population, the elite population, consists of the best individuals,
whereas the larger population contains less fit individuals. These populations
have different characteristics, such as size and mutation probability, based on
the fitness of the candidate solutions in these populations. The performance of
our 2PGA is compared to that of a single population genetic algorithm (SPGA).
Because the 2PGA has multiple parameters, the significance and the effect of the
parameters is also studied. Experimental results show that the 2PGA outperforms
the SPGA reliably without increasing the amount of fitness function evaluations.
Although genetic algorithms are used as a platform for the 2PGA scheme, the
principles presented here are applicable also to other population based
evolutionary optimization methods.
Heuristic
Methods for Automatic Rotating Workforce Scheduling
Nysret Musliu
Vienna University of Technology
Karlsplatz 13, 1040 Wien, Austria
Abstract:
Rotating workforce scheduling appears in different forms in a broad range of
workplaces, such as industrial plants, call centers, public transportation, and
airline companies. It is of a high practical relevance to find workforce
schedules that fulfill the ergonomic criteria of the employees, and reduce costs
for the organization. In this paper we propose new heuristic methods for
automatic generation of rotating workforce schedules. To improve the quality of
each heuristic method alone, we further propose the hybridization of these
methods. The following methods are proposed: (1)A Tabu Search (TS) based
algorithm, (2) A heuristic method based on min-conflicts heuristic (MC), (3) A
method that includes in the tabu search algorithm the min-conflicts heuristic
(TS-MC) and random walk (TS-RW), (4) A method that includes in the min-conflicts
heuristic the tabu mechanism (MC-T), random walk (MC-RW), and both the tabu
mechanism and the random walk (MC-T-RW). The appropriate neighborhood structure,
tabu mechanism, and fitness function, based on the specifics of the problem are
proposed. The proposed methods are implemented and experimentally evaluated on
the benchmark examples given in the literature and on the real life test
problems, which we collected from a broad range of organizations. Empirical
results show that the combination of the min-conflicts heuristic with tabu
search can be used to solve this problem very effectively. The hybrid methods
improve the performance of the commercial system for generation of rotating
workforce schedules and are currently in the process of being included in a
commercial package for automatic generation of rotating workforce schedules.
A Multiple Neural
Network System to Classify Solder Joints on Integrated Circuits
G. Acciani, G. Brunetti and G. Fornarelli
Politecnico di Bari, Dipartimento di Elettrotecnica ed Elettronica,
Via E. Orabona 4, Bari 70125, Italy
Abstract: The following paper introduces a diagnostic process to detect
solder joint defects on Printed Circuit Boards assembled in Surface Mounting
Technology. The diagnosis is accomplished by a Neural Network System which
processes the images of the solder joints of the integrated circuits mounted on
the board. The board images are acquired and then preprocessed to extract the
regions of interest for the diagnosis which are the solder joints of the
integrated circuits. Five different levels of solder quality in respect to the
amount of solder paste have been defined. Two feature vectors have been
extracted from each region of interest, the “geometric” feature vector and the
“wavelet” feature vector. Both vectors feed the neural network system
constituted by two Multi Layer Perceptron neural networks and a Linear Vector
Quantization network for the classification. The experimental results are
devoted to comparing the performances of a Multi Layer Perceptron network, of a
Linear Vector Quantization network, and of the overall neural network system,
considering both geometric and wavelet features. The results prove that the
overall classifier is the best compromise in terms of recognition rate and time
required for the diagnosis in respect to the single classifiers.
Mathematical
Analysis of the Heuristic Optimisation Mechanism of Evolutionary Programming
Libao Shi1,2, Zhao Yang Dong1, Jin Hao3 and Kit
Po Wong4
1 School of Information Technology and Electrical Engineering, The
University of Queensland, St Lucia, QLD 4072 Australia
2National key laboratory of power systems in Shenzhen, Tsinghua
University, Tsinghua Campus, The University Town, Shenzhen, 518055
3 Department of Electrical and Computer Engineering, The University
of Alberta, Edmonton, Alberta, Canada
4 Department of Electrical engineering, The Hong Kong Polytechnic
University, Hong Kong
Abstract: Evolutionary algorithms are robust and adaptive. They have
found a wide variety of applications solving optimisation and search problems.
As one of the main stream algorithms in evolutionary computation evolutionary
programming (EP) mainly uses real values of parameters. This makes it very
attractive for many engineering optimisation applications. In addition to the
evolutionary characteristics more in depth dynamic optimisation mechanisms of EP
is investigated in this paper. An optimisation model based on differential
equations is developed to explore and exploit the inherent optimal operation
process of EP. The proposed model is based on the characteristics of population
evolution and uses two performance measures, (i) Population On-line Performance
measure and (ii) Population Off-line Performance measure. These two measures are
used to quantify the dynamic population optimisation of EP and to form the
foundation for the construction of the differential equation based optimisation
model. The model is proposed with strict theoretical and numerical analysis. A
number of important conclusions and observations are presented in accordance
with the analytical results.
Nonlinear Image
Enhancement to Improve Face Detection in Complex Lighting Environment
Li Tao, Ming-Jung Seow and Vijayan K. Asari
Computational Intelligence and Machine Vision Laboratory
Department of Electrical and Computer Engineering
Old Dominion University, Norfolk, VA 23529
Abstract: A robust and efficient image enhancement technique has been developed
to improve the visual quality of digital images that exhibit dark shadows due to
the limited dynamic ranges of imaging and display devices which are incapable of
handling high dynamic range scenes. The proposed technique processes images in
two separate steps: dynamic range compression and local contrast enhancement.
Dynamic range compression is a neighborhood dependent intensity transformation
which is able to enhance the luminance in dark shadows while keeping the overall
tonality consistent with that of the input image. The image visibility can be
largely and properly improved without creating unnatural rendition in this
manner. A neighborhood dependent local contrast enhancement method is used to
enhance the images contrast following the dynamic range compression.
Experimental results on the proposed image enhancement technique demonstrates
strong capability to improve the performance of convolutional face finder
compared to histogram equalization and multiscale Retinex with color restoration
without compromising the false alarm rate.