Skip to main content
main-content

Über dieses Buch

This book describes recent advances on hybrid intelligent systems using soft computing techniques for diverse areas of application, such as intelligent control and robotics, pattern recognition, time series prediction and optimization complex problems. Soft Computing (SC) consists of several intelligent computing paradigms, including fuzzy logic, neural networks and bio-inspired optimization algorithms, which can be used to produce powerful hybrid intelligent systems. The book is organized in five main parts, which contain a group of papers around a similar subject. The first part consists of papers with the main theme of type-2 fuzzy logic, which basically consists of papers that propose new models and applications for type-2 fuzzy systems. The second part contains papers with the main theme of bio-inspired optimization algorithms, which are basically papers using nature-inspired techniques to achieve optimization of complex optimization problems in diverse areas of application. The third part contains papers that deal with new models and applications of neural networks in real world problems. The fourth part contains papers with the theme of intelligent optimization methods, which basically consider the proposal of new methods of optimization to solve complex real world optimization problems. The fifth part contains papers with the theme of evolutionary methods and intelligent computing, which are papers considering soft computing methods for applications related to diverse areas, such as natural language processing, recommending systems and optimization.

Inhaltsverzeichnis

Frontmatter

Type-2 Fuzzy Logic

Frontmatter

Genetic Algorithm Optimization for Type-2 Non-singleton Fuzzy Logic Controllers

In this chapter we study the automatic design of type-2 non-singleton fuzzy logic controller. To test the controller we use an autonomous mobile robot for the trajectory tracking control. We take the basis of the interval type-2 fuzzy logic controller of previous work for the extension to the type-2 non-singleton fuzzy logic controller. A genetic algorithm is used to obtain an automatic design of the type-2 non-singleton fuzzy logic controller (NSFLC). Simulation results are obtained with Simulink showing the behavior of the mobile robot whit this type of controller.

Ricardo Martínez-Soto, Oscar Castillo, Juan R. Castro

Hierarchical Genetic Algorithms for Type-2 Fuzzy System Optimization Applied to Pattern Recognition and Fuzzy Control

In this chapter a new method of hierarchical genetic algorithm for fuzzy inference systems optimization is proposed. This method was used in two applications, the first was to perform the combination of responses of modular neural networks for human recognition based on face, iris, ear and voice, and the second one for fuzzy control of temperature in the shower benchmark problem. The results obtained by non-optimized type-2 fuzzy inference system can be improved using the proposed hierarchical genetic algorithm as can be verified by the simulations.

Daniela Sánchez, Patricia Melin

Designing Type-2 Fuzzy Systems Using the Interval Type-2 Fuzzy C-Means Algorithm

In this work, the Interval Type-2 Fuzzy C-Mean (IT2FCM) algorithm was used for the design of Type-2 Fuzzy Inference Systems using centroids and fuzzy membership matrices for the lower and upper bound of the interval obtained by the IT2FCM algorithm in each data clustering realized by this algorithm, with these elements obtained by IT2FCM algorithm we design the Mamdani, and Sugeno Fuzzy Inference systems for classification of data sets and time series prediction.

Elid Rubio, Oscar Castillo

Neural Network with Fuzzy Weights Using Type-1 and Type-2 Fuzzy Learning with Gaussian Membership Functions

In this chapter type-1 and type-2 fuzzy inferences systems are used to obtain the type-1 or type-2 fuzzy weights in the connection between the layers of a neural network. We used two type-1 or type-2 fuzzy systems that work in the backpropagation learning method with the type-1 or type-2 fuzzy weight adjustment. The mathematical analysis of the proposed learning method architecture and the adaptation of type-1 or type-2 fuzzy weights are presented. The proposed method is based on recent methods that handle weight adaptation and especially fuzzy weights. In this work neural networks with type-1 fuzzy weights or type-2 fuzzy weights are presented. The proposed approach is applied to the case of Mackey–Glass time series prediction.

Fernando Gaxiola, Patricia Melin, Fevrier Valdez

A Comparative Study of Membership Functions for an Interval Type-2 Fuzzy System used to Dynamic Parameter Adaptation in Particle Swarm Optimization

This chapter present an analysis of the effects in quality results that brings the different types of membership functions in an interval type-2 fuzzy system used to adapt some parameters of Particle Swarm Optimization (PSO). Benchmark mathematical functions are used to test the methods and a comparison is performed.

Frumen Olivas, Fevrier Valdez, Oscar Castillo

Genetic Optimization of Type-2 Fuzzy Integrators in Ensembles of ANFIS Models for Time Series Prediction

This chapter describes the genetic optimization of interval type-2 fuzzy integrators in Ensembles of ANFIS (adaptive neuro-fuzzy inferences systems) models for the prediction of the Mackey-Glass time series. The considered a chaotic system is he Mackey-Glass time series that is generated from the differential equations, so this benchmarks time series is used for the test of performance of the proposed ensemble architecture. We used the interval type-2 and type-1 fuzzy systems to integrate the output (forecast) of each Ensemble of ANFIS models. Genetic Algorithms (GAs) were used for the optimization of memberships function parameters of each interval type-2 fuzzy integrators. In the experiments we optimized Gaussians, Generalized Bell and Triangular membership functions for each of the fuzzy integrators, thereby increasing the complexity of the training. Simulation results show the effectiveness of the proposed approach.

Jesus Soto, Patricia Melin

Ensemble Neural Network Optimization Using the Particle Swarm Algorithm with Type-1 and Type-2 Fuzzy Integration for Time Series Prediction

This chapter describes the design of ensemble neural networks using Particle Swarm Optimization for time series prediction with Type-1 and Type-2 Fuzzy Integration. The time series that is being considered in this work is the Mackey-Glass benchmark time series. Simulation results show that the ensemble approach produces good prediction of the Mackey-Glass time series.

Martha Pulido, Patricia Melin

Uncertainty-Based Information Granule Formation

A new technique for forming information granules is shown in this chapter. Based on the theory of uncertainty-based information, an approach is proposed which forms Interval Type-2 Fuzzy information granules. This approach captures multiple evaluations of uncertainty from taken samples and uses these models to measure the uncertainty from the difference in these. The proposed approach is tested through multiple benchmark datasets: iris, wine, glass, and a 5th order curve identification.

Mauricio A. Sanchez, Oscar Castillo, Juan R. Castro

A Type 2 Fuzzy Neural Network Ensemble to Estimate Time Increased Probability of Seismic Hazard in North Region of Baja California Peninsula

A type-2 adaptive fuzzy neural network ensemble approach is presented here to achieve the prediction of seismic events of M

0

magnitude in the north region of the Baja California Peninsula. Three algorithms are used with the ensemble: data analysis, M8 and CN. Seismic data coordinates are used in probabilistic fuzzy sets that are processed in the three fuzzy neural networks that integrate the ensemble to generate an output of a probabilistic set of predictions.

Victor M. Torres, Oscar Castillo

Bio-Inspired Algorithms

Frontmatter

Shipwrecked on Fear: Selection of Electives in School Minorities in a University Using Cuckoo Search Algorithm

The purpose of this research is to understand from a Multivariable optimization related with four scholar minorities studies in a University with approximately 87 educational studies on Bachelor level, this sample is composed by: (Safety Sciences, Interior Design, Sports Training and Aeronautics) assuming that any student want to analyze the way in which these minority groups selected electives to complete the set of credits in their respective studies to determine the optimal selection which involve the choice of these materials in educational majority groups to determine the benefit-cost associated with the term professional studies, whose main base the restriction on a small number of subjects in their studies this because such a low minority enrollment, even though this problem has been studied repeatedly by many researchers on the literature have not been established optimal values by supporting bio-inspired algorithms to interact with the different values associated with the achievement of the term loans and the cost-benefit every student to a minority group and comparing their choices of electives with respect the group. There are several factors that can influence the selection of an elective, for our research we propose to use a new bio-inspired algorithm called “Cuckoo search algorithm,” which has proven effective for the cohesion of behavior associated with several problems, and when and use restrictions have strategies to keep tempo in the selection of these materials, in our case, a resource such as time gain regarding the subjects studied is represented as the optimal way for the duration of the professional studies with uncertainty not know how long it can last set appropriate conditions for the selection of specialized subjects.

Alberto Ochoa-Zezzatti, Oscar Castillo, Patricia Melín, Nemesio Castillo, Sandra Bustillos, Julio Arreola

An Admission Control and Channel Allocation Algorithm Based on Particle Swarm Optimization for Cognitive Cellular Networks

During the last few years cellular networks have increased the use of spectrum resources due to the success of mobile broadband services. Mobile devices generate more data than ever before, facing the way cellular networks are deployed today to meet the ever increasing traffic demand. Making new exclusive spectrum available to meet traffic demand is challenging since spectrum resources are finite, therefore costly. Cognitive radio technology is proposed, for conventional cellular networks, as a solution to enlarge the pool of available spectrum resources for mobile users through femtocells (small cells), overlaid on the existing macrocell network, to share a common spectrum. However, by reusing simultaneously spectrum resources from femto networks, potentially destructive interference on macro networks is introduced. In this context, we present a femto-users admission control and channel allocation algorithm based on Particle Swarm Optimization (PSO) to maintain the interference to a required Quality of Service (QoS) level in macro-femto networks while, at the same time, data rate is maximized in the whole system. The proposed approach provides design requirements for deploying future cognitive cellular networks.

Anabel Martínez-Vargas, Ángel G. Andrade, Roberto Sepúlveda, Oscar Montiel-Ross

Optimization of Fuzzy Controllers Design Using the Bee Colony Algorithm

In this chapter we present the application of the optimization method using bee colony (BCO for its acronym in English, Bee Colony Optimization), for optimizing fuzzy controllers, BCO is a heuristic technique inspired by the behavior of honey bees in the nature, to solve optimization problems. This was tested in two BCO optimization problems, one optimized set of mathematical functions for twenty to fifty dimensions, and two fuzzy controllers’ optimization. The results are compared with other bio-inspired algorithms state of the art, of which we highlight that there is a lot of competition in terms of quality and consistency in the results, even if the method is one of the latest in the field of collective intelligence. Similarly presents some interesting observations derived from observed performance.

Camilo Caraveo, Oscar Castillo

Optimization of Benchmark Mathematical Functions Using the Firefly Algorithm

Nature-inspired algorithms are more relevant today, such as PSO and ACO, which have been used in various types of problems such as the optimization of neural networks, fuzzy systems, control, and others showing good results. There are other methods that have been proposed more recently, the firefly algorithm is one of them, this paper will explain the algorithm and describe how it behaves. In this chapter the firefly algorithm was applied in optimizing benchmark functions and comparing the results of the same functions with genetic algorithms.

Cinthya Solano-Aragón, Oscar Castillo

Optimization of Fuzzy Control Systems for Mobile Robots Based on PSO

This paper describes the optimization of a navigation controller system for a mobile autonomous robot using the PSO algorithm to adjust the parameters of each fuzzy controller, the navigation system is composed of 2 main controllers, a tracking controller and a reactive controller, plus an integrator block control that combines both fuzzy inference systems (FIS). The integrator block is called Weighted Fuzzy Inference System (WFIS) and assigns weights to the responses in each block of behavior in order to combine them into a single response. A comparison with the results obtained with genetic algorithms is also performed.

David de la O, Oscar Castillo, Abraham Meléndez

Design of a Fuzzy System for Flight Control of an F-16 Airplane

In this paper the main idea is to control the flight of an F-16 airplane using fuzzy system and PID controller to achieve the control. In general, to control the total flight is necessary to control the angle of the elevator, angle of the aileron and the angle of the rudder. For this reason, 3 fuzzy systems are used to control the respective angles. In this paper the fuzzy systems are presented with results using the simulation plant of the airplane.

Leticia Cervantes, Oscar Castillo

Bat Algorithm Comparison with Genetic Algorithm Using Benchmark Functions

We describe in this chapter a Bat Algorithm and Genetic Algorithm (GA) conducting a performance comparison of the two algorithms Benchmark testing them in mathematical functions, parameters adjustment is done manually for both algorithms in 6 math functions, including some references on work done with the bat and area algorithm optimization with mathematical functions.

Jonathan Pérez, Fevrier Valdez, Oscar Castillo

Comparative Study of Social Network Structures in PSO

In this chapter a comparative study of social network structures in Particle Swarm Optimization is performed. The social networks employed by the

gbest

PSO and

lbest

PSO algorithms are star, ring, Von Neumann and random topologies. Each topology is implemented on four benchmark functions. The objective is knows the performance between each topology with different dimensions. Benchmark functions were used such as Rastrigin, Griewank, Rosenbrock and Sphere.

Juan Carlos Vazquez, Fevrier Valdez, Patricia Melin

Comparison of the Optimal Design of Fuzzy Controllers for the Water Tank Using Ant Colony Optimization

A study of the behavior and evaluation of the Ant Colony Optimization algorithm (ACO) in Type-1 and Type-2 Fuzzy Controller design is presented in this chapter. The main objective of the work is based on the main reasons in tuning membership functions for the optimization Fuzzy Controllers of the benchmark problem known as the Water Tank with the algorithm of Ant Colony Optimization. For the design of Type-1 and Type-2 Fuzzy Controllers for particular applications, the use of bio-inspired optimization methods have helped in the complex task of finding the appropriate values of the parameters and the structure of fuzzy systems. In this research we consider the application of ACO as the paradigm that aids in the optimal design of Type-1 and Type-2 Fuzzy Controllers. We also analyzed that in evaluating the uncertainty, the results in the simulation are better with Type-2 Fuzzy Controllers. Finally, provide a comparison of the different methods for the case of designing Type-1 and Type-2 Fuzzy Controllers with Ant Colony Optimization.

Leticia Amador-Angulo, Oscar Castillo

Differential Evolution with Dynamic Adaptation of Parameters for the Optimization of Fuzzy Controllers

The proposal described in this chapter uses the Differential Evolution (DE) algorithm as an optimization method in which we want to dynamically adapt its parameters using fuzzy logic control systems, with the goal that the fuzzy system gives the optimal parameter of the DE algorithm to find better results, depending on the type of problems the DE is applied.

Patricia Ochoa, Oscar Castillo, José Soria

A Fuzzy Control Design for an Autonomous Mobile Robot Using Ant Colony Optimization

In this chapter we describe the methodology to design an optimized fuzzy logic controller for an autonomous mobile robot, using Ant Colony Optimization (ACO). This is achieved by applying a systematic and hierarchical optimization modifying the conventional ACO algorithm using ants partition. The simulations results proved that the proposed algorithm performs even better that the classic ACO algorithm when optimizing membership functions of FLC, parameters and fuzzy rules.

Evelia Lizarraga, Oscar Castillo, José Soria, Fevrier Valdez

Neural Networks

Frontmatter

Optimization of Modular Neural Networks with the LVQ Algorithm for Classification of Arrhythmias Using Particle Swarm Optimization

In this chapter we describe the application of a full model of PSO as an optimization method for modular neural networks with the LVQ algorithm in order to find the optimal parameters of a modular architecture for the classification of arrhythmias. Simulation results show that this modular model optimized with PSO achieves acceptable classification rates for the MIT-BIH arrhythmia database with 15 classes.

Jonathan Amezcua, Patricia Melin

A DTCNN Approach on Video Analysis: Dynamic and Static Object Segmentation

This paper presents a DTCNN model for dynamic and static object segmentation in videos. The proposed method involves three main stages in the dynamic stage; dynamic background registration, dynamic objects detection and object segmentation improvement. Two DTCNNs are used, one to achieved object detection and other for morphologic operations in order to improve object segmentation. The static segmentation stage is composed of a clustering module and a DTCNN module. The clustering module is in charge of detecting the possible regions and the DTCNN generate the regions. Visual and quantitative results indicate acceptable results compared with existing methods.

Mario I. Chacon-Murguia, David Urias-Zavala

Identification of Epilepsy Seizures Using Multi-resolution Analysis and Artificial Neural Networks

Finding efficient and effective automatic methods for the identification and prediction of epileptic seizures is highly desired, due to the relevance of this brain disorder. Despite the large amount of research going on in identification and prediction solutions, still it is required to find confident methods suitable to be used in real applications. In this paper, we discuss the principal challenges found in epilepsy identification, when it is carried on offline analyzing electro-encephalograms (EEG) recordings. Indeed, we present the results obtained so far in our research group, with a system based on multi-resolution analysis and feed-forward neural networks, which focus on tackling three important challenges found in this type of problems: noise reduction, feature extraction and pertinence of the classifier. A

3

-

fold

validation of our strategy reported an accuracy of 99.26 ± 0.26 %, a sensitive of 98.93 % and a specificity of 99.59 %, using data provided by the University of Bonn. Several combinations of filters and wavelet transforms were tested, found that the best results occurs when a Chebyshev II filter was used to eliminate noise, 5 characteristics were obtained using a Discrete Wavelet Transform (DWT) with a Haar wavelet and a feed-forward neural network with 18 hidden nodes was used for classification.

Pilar Gómez-Gil, Ever Juárez-Guerra, Vicente Alarcón-Aquino, Manuel Ramírez-Cortés, José Rangel-Magdaleno

Temporal Validated Meta-Learning for Long-Term Forecasting of Chaotic Time Series Using Monte Carlo Cross-Validation

Forecasting long-term values of chaotic time series is a difficult task, but it is required in several domains such as economy, medicine and astronomy. State-of-the-art works agree that the best accuracy can be obtained combining forecasting models. However, selecting the appropriate models and the best way to combine them is an open problem. Some researchers have been focusing on using prior knowledge of the performance of the models for combining them. A way to do so is by meta-learning, which is the process of automatically learning from tasks and models showing the best performances. Nevertheless, meta-learning in time series impose no trivial challenges; some requirements are to search the best model, to validate estimations, and even to develop new meta-learning methods. The new methods would consider performance variances of the models over time. This research addresses the meta-learning problem of how to select and combine models using different parts of the prediction horizon. Our strategy, called “Temporal Validated Combination” (TVC), consists of splitting the prediction horizon into three parts: short, medium and long-term windows. Next, for each window, we extract knowledge about what model has the best performance. This knowledge extraction uses a Monte Carlo cross-validation process. Using this, we are able to improve the long-term prediction using different models for each prediction window. The results reported in this chapter show that TVC obtained an average improvement of 1 % in the prediction of 56 points of the NN5 time series, when compared to a combination of best models based on a simple average. NARX neural networks and ARIMA models were used for building the predictors and the SMAPE metric was used for measuring performances.

Rigoberto Fonseca, Pilar Gómez-Gil

MLP for Electroencephalographic Signals Classification Using Different Adaptive Learning Algorithm

For the identification of muscular pain caused by a puncture in the right arm and eye blink, electroencephalographic (EEG) signals are analyzed in the frequency and temporal domain. EEG activity was recorded from 15 subjects in range of 23–25 years of age, while pain is induced and during blinking. On the other hand, EEG was converted from time to frequency domain using the Fast Fourier Transform (FFT) for being classified by an Artificial Neural Network (ANN). Experimental results in the frequency and time domain using five adaptation algorithms show that both neural network architecture proposals for classification produce successful results.

Roberto Sepúlveda, Oscar Montiel, Daniel Gutiérrez, Gerardo Díaz, Oscar Castillo

Chemical Optimization Method for Modular Neural Networks Applied in Emotion Classification

The goal of this chapter is the classification of the voice transmitted emotions, and in order to achieve it we worked with the Mel cepstrum coefficients for the pre-processing of audio. We also used a Modular Neural Network as the classification method and a new optimization algorithm was implemented: Chemical Reaction Algorithm which hadn’t been used before on the optimization of neural networks to find the architecture of the neural network optimizing the number of layers in each module and the number of neurons by layer. The tests were executed on the Berlin Emotional Speech data base, which was recorded by actors in German language in six different emotional states of which they only considered anger, happiness and sadness.

Coral Sánchez, Patricia Melin, Leslie Astudillo

Comparing Metaheuristic Algorithms on the Training Process of Spiking Neural Networks

Spiking Neural Networks are considered as the third generation of Artificial Neural Networks. In these networks, spiking neurons receive/send the information by timing of events (spikes) instead by the spike rate; as their predecessors do. Spikeprop algorithm, based on gradient descent, was developed as learning rule for training SNNs to solve pattern recognition problems; however this algorithm trends to be trapped in local minima and has several limitations. For dealing with the supervised learning on Spiking Neural Networks without the drawbacks of Spikeprop, several metaheuristics such as: Evolutionary Strategy, Particle Swarm Optimization, have been used to tune the neural parameters. This work compares the performance and the impact of some metaheuristics used for training spiking neural networks.

Andrés Espinal, Martín Carpio, Manuel Ornelas, Héctor Puga, Patricia Melin, Marco Sotelo-Figueroa

A Hybrid Method Combining Modular Neural Networks with Fuzzy Integration for Human Identification Based on Hand Geometric Information

In this chapter a hybrid approach for human identification based on the hand geometric information is presented. The hybrid approach is based on using modular neural networks and fuzzy logic in a synergetic fashion to achieve effective and accurate hand biometric identification. Modular neural networks are used to recognize hand images based on the geometric information. Fuzzy logic is used to combine the performed recognition from several modular neural networks and the same time handle the uncertainty in the data. The proposed hybrid approach was implemented and tested with a benchmark database and experimental results show competitive identification rates when compared with the best methods proposed by other authors.

José Luis Sánchez, Patricia Melin

Echocardiogram Image Recognition Using Neural Networks

In this chapter we present a neural network architecture to recognize if the echocardiogram image corresponds to a person with a heart disease or is an image of a person with a normal heart, so that it can facilitate the medical diagnosis of the person that may hold an illness. One of the most used methods for the detection and analysis of diseases in the human body by doctors and specialists is the use of medical imaging. These images become one of the possible means to achieve a safe estimate of the severity of the injuries and thus to initiate treatment for the benefit of the patient.

Beatriz González, Fevrier Valdez, Patricia Melin, German Prado-Arechiga

Face Recognition with Choquet Integral in Modular Neural Networks

In this chapter a new method for response integration, based on Choquet Integral is presented. A type-1 fuzzy system for edge detections based in Sobel and Morphological gradient is used, which is a pre-processing applied to the training data for better performance in the modular neural network. The Choquet integral is used how method to integrate the outputs of the modules of the modular neural networks (MNN). A database of faces was used to perform the pre-processing, the training, and the combination of information sources of the MNN.

Gabriela E. Martínez, Patricia Melin, Olivia D. Mendoza, Oscar Castillo

Optimization Methods and Applications

Frontmatter

A Survey of Decomposition Methods for Multi-objective Optimization

The multi-objective optimization methods are traditionally based on Pareto dominance or relaxed forms of dominance in order to achieve a representation of the Pareto front. However, the performance of traditional optimization methods decreases for those problems with more than three objectives to optimize. The decomposition of a multi-objective problem is an approach that transforms a multi-objective problem into many single-objective optimization problems, avoiding the need of any dominance form. This chapter provides a short review of the general framework, current research trends and future research topics on decomposition methods.

Alejandro Santiago, Héctor Joaquín Fraire Huacuja, Bernabé Dorronsoro, Johnatan E. Pecero, Claudia Gómez Santillan, Juan Javier González Barbosa, José Carlos Soto Monterrubio

A Decision Support System Framework for Public Project Portfolio Selection with Argumentation Theory

In this chapter, we propose a framework for a Decision Support System (DSS) to aid in the selection of public project portfolios. Organizations are investing continuously and simultaneously in projects, however, they face the problem of having more projects than resources to implement them. Public projects are designed to favor society. Researches have commonly addressed the public portfolio selection problem with multicriteria algorithms, due to its high dimensionality. These algorithms focus on identifying a set of solutions in the Pareto frontier. However, the selection of the solution depends on the changing criteria of the decision maker (DM). A framework to support the DM is presented; it is designed to help the DM by a dialogue game to select the best portfolio in an interactive way. The framework is based on the argumentation theory and a friendly user interface. The dialogue game allows the DM to ask for justification on the project portfolio selection.

Laura Cruz-Reyes, César Medina Trejo, Fernando López Irrarragorri, Claudia G. Gómez Santillán

Generic Memetic Algorithm for Course Timetabling ITC2007

Course timetabling is an important and recurring administrative activity in most educational institutions. This chapter describes an automated configuration of a generic memetic algorithm to solving this problem. This algorithm shows competitive results on well-known instances compared against top participants of the most recent International ITC2007 Timetabling Competition. Importantly, our study illustrates a case where generic algorithms with increased autonomy and generality achieve competitive performance against human designed problem-specific algorithms.

Soria-Alcaraz Jorge, Carpio Martin, Puga Hector, Melin Patricia, Terashima-Marin Hugo, Cruz Laura, Sotelo-Figueroa Marco

Characterization of the Optimization Process

Recent works in experimental analysis of algorithms have identified the need to explain the observed performance. To understand the behavior of an algorithm it is necessary to characterize and study the factors that affect it. This work provides a summary of the main works related to the characterization of heuristic algorithms, by comparing the works done in understanding how and why algorithms follow certain behavior. The main objective of this research is to promote the improvement of the existing characterization methods and contribute to the development of methodologies for robust analysis of heuristic algorithms performance. In particular, this work studies the characterization of the optimization process of the Bin Packing Problem, exploring existing results from the literature, showing the need for further performance analysis.

Marcela Quiroz, Laura Cruz-Reyes, Jose Torres-Jimenez, Claudia Gómez Santillán, Héctor J. Fraire Huacuja, Patricia Melin

A New Integer Linear Programming Model for the Cutwidth Minimization Problem of a Connected Undirected Graph

In this chapter we propose a new integer linear programming model based on precedences for the cutwidth minimization problem (CWP). A review of the literature indicates that this model is the only one reported for this problem. The results of the experiments with standard instances shows that the solution of the problem with the proposed model outperforms in quality and efficiency to the one reported in the state of the art. Our model increases the number of optimal solutions by 38.46 % and the gap reduction by 45.56 %. Moreover, this quality improvement is reached with a time solution reduction of 41.73 %. It is considered that the approach used in this work can be used in other linear ordering problems.

Mario C. López-Locés, Norberto Castillo-García, Héctor J. Fraire Huacuja, Pascal Bouvry, Johnatan E. Pecero, Rodolfo A. Pazos Rangel, Juan J. G. Barbosa, Fevrier Valdez

On the Exact Solution of VSP for General and Structured Graphs: Models and Algorithms

In this chapter the vertex separation problem (VSP) is approached. VSP is NP-hard with important applications in VLSI, computer language compiler design, and graph drawing, among others. In the literature there are several exact approaches to solve structured graphs and one work that proposes an integer linear programming (ILP) model for general graphs. Nevertheless, the model found in the literature generates a large number of variables and constraints, and the approaches for structured graphs assume that the structure of the graphs is known a priori. In this work we propose a new ILP model based on a precedence representation scheme, an algorithm to identify whether or not a graph has a Grid structure, and a new benchmark of scale-free instances. Experimental results show that our proposed ILP model improves the average computing time of the reference model in 79.38 %, and the algorithm that identifies Grid-structured graphs has an effectiveness of 100 %.

Norberto Castillo-García, Héctor Joaquín Fraire Huacuja, Rodolfo A. Pazos Rangel, José A. Martínez Flores, Juan Javier González Barbosa, Juan Martín Carpio Valadez

Preference Incorporation into Evolutionary Multiobjective Optimization Using a Multi-Criteria Evaluation Method

Most approaches in the evolutionary multiobjective optimization literature concentrate mainly on generating an approximation of the Pareto front. However, this does not completely solve the problem since the Decision Maker (DM) still has to choose the best compromise solution out of that set. This task becomes difficult when the number of criteria increases. In this chapter, we introduce a new way to incorporate and update the DM’s preferences into a Multiobjective Evolutionary Algorithm, expressed in a set of solutions assigned to ordered categories. We propose a variant of the well-known Non-dominated Sorting Genetic Algorithm II (NSGA-II), called Hybrid-MultiCriteria Sorting Genetic Algorithm (H-MCSGA). In this algorithm, we strengthen the selective pressure based on dominance adding selective pressure based on assignments to categories. Particularly, we make selective pressure towards non-dominated solutions that belong to the best category. In instances with 9 objectives on the project portfolio problem, H-MCSGA outperforms NSGA-II obtaining non-dominated solutions that belong to the most preferred category.

Laura Cruz-Reyes, Eduardo Fernandez, Claudia Gomez, Patricia Sanchez

A Loading Procedure for the Containership Stowage Problem

This chapter deals with the containership stowage problem. It is an NP-hard combinatorial optimization whose goal is to find optimal plans for stowing containers into a containership with low operational costs, subject to a set of structural and operational constraints. In order to optimize a stowage planning, like in the literature, we have developed an approach that decomposes the problem hierarchically. This approach divides the problem into two phases: the first one consists of generating a relaxed initial solution, and the second phase is intended to make this solution feasible. In this chapter, we focus on the first phase of this approach, and a new loading procedure to generate an initial solution is proposed. This procedure produces solutions in short running time, so that, it could be applied to solve real instances.

Laura Cruz-Reyes, Paula Hernández Hernández, Patricia Melin, Héctor Joaquín Fraire Huacuja, Julio Mar-Ortiz, Héctor José Puga Soberanes, Juan Javier González Barbosa

Quality-Assessment Model for Portfolios of Projects Expressed by a Priority Ranking

Organizations need to make decisions about how to invest and manage the resources to get more benefits, but, commonly the organization’s resources are not enough to support all project proposals. Thus, the decision maker (DM) wants to select the portfolio with the highest contribution to the organizational objectives. But in many practical cases, to know exactly the benefits associated to implement each proposal is too difficult, therefore it is questionable the issue of evaluating portfolio quality in these conditions In order to face these uncertainty situations, the DM usually ranks the applicant projects according to his/her preferences about an estimated impact of each portfolio. However, a correct modeling of the quality of the portfolio is indispensable to develop a model of coherent optimization to the ranking given by the DM. In the literature, this type of problems has been scantily approached in spite of being present in many practical situations of assignment of resources. In this Chapter we propose a quality model of portfolio and an algorithm that solves it. The experimental results show that the algorithm that includes our model offers benefits to the decision maker, and his advantages highlighted with respect to the related works reported in the state of the art.

S. Samantha Bastiani, Laura Cruz-Reyes, Eduardo Fernandez, Claudia Gómez, Gilberto Rivera

Exact Methods for the Vertex Bisection Problem

In this chapter we approach the vertex bisection problem (VB), which is relevant in the context of communication networks. A literature review shows that the reported exact methods are restricted to solve particular graph cases. As a first step to solve the problem for general graphs using soft computing techniques, we propose two new integer-linear programming models and a new branch and bound algorithm (B&B). For the first time, the optimal solutions for an extensive set of standard instances were obtained.

Héctor Fraire, J. David Terán-Villanueva, Norberto Castillo García, Juan Javier Gonzalez Barbosa, Eduardo Rodríguez del Angel, Yazmín Gómez Rojas

Evolutionary and Intelligent Methods

Frontmatter

Using a Graph Based Database to Support Collaborative Interactive Evolutionary Systems

Web based, collaborative, interactive evolutionary computational systems, can generate a high amount of information. There is information regarding users and their collaborations, the interaction and subjective evaluation of individuals of the population. There is also information about the actual evolutionary process: relationships between individuals and evolutionary operators, used. In this work we propose the use of graph-based databases as back end storage of the evolutionary process of collaborative interactive evolutionary systems due to the expressiveness and flexibility provided by the model and how relationships found on the system can be easily mapped to graphs. The flexibility provided enables the design of user models, social network modules that can enhance the system. As a proof of concept, a comparative implementation against a relational database is presented.

J. C. Romero, M. García-Valdez

Fuzzy Labeling of Users in an Educational Intelligent Environment Using an Activity Stream

This chapter presents a method for labeling users in an intelligent environment according to activities drawn from an activity stream. The activity stream is composed by all the activities that are registered in a certain window of time. Using a fuzzy inference engine labels are assigned to students, in order to aggregate the generated data. To evaluate the scalability of the approach several simulations where executed, results show the method is viable tool.

Francisco Arce, Mario García-Valdez

Automatic Estimation of Flow in Intelligent Tutoring Systems Using Neural Networks

Flow is a mental state where a person is fully focused on an activity, and is enjoying performing it. Mihaly Csikszentmihalyi, who coined the concept, defines flow in terms of the skill and challenge levels of the activity as perceived by the person performing such activity. In this chapter, we propose the use of neural networks to predict if a student, after completing a computer-programming problem, is in a state of flow or not. To do so, we performed an experiment where we apply a very basic computer-programming tutorial to 21 students. We registered in a database how much time it took the students to finish the test, how many keystrokes they needed to press before achieving the goals of each exercise, how much time it took the student to start trying to solve the problem, the time between each keystroke, and how many attempts the student needed before successfully completing each exercise. Using these variables, we built a neural network that was capable of predicting if a student was in flow or not after the completion of each problem in the tutorial.

Amaury Hernandez, Mario Garcia, Alejandra Mancilla

Features and Pitfalls that Users Should Seek in Natural Language Interfaces to Databases

Natural Language Interfaces to Databases (NLIDBs) are tools that can be useful in making decisions, allowing different types of users to get information they need using natural language communication. Despite their important features and that for more than 50 years NLIDBs have been developed, their acceptance by end users is very low due to extremely complex problems inherent to natural language, their customization and internal operation, which has produced poor performance regarding queries correctly translated. This chapter presents a study on the main desirable features that NLIDBs should have as well as their pitfalls, describing some study cases that occur in some interfaces to illustrate the flaws of their approach.

Rodolfo A. Pazos Rangel, Marco A. Aguirre, Juan J. González, Juan Martín Carpio

Step Length Estimation and Activity Detection in a PDR System Based on a Fuzzy Model with Inertial Sensors

This chapter presents an approach on pedestrian dead reckoning (PDR) which incorporates activity classification over a fuzzy inference system (FIS) for step length estimation. In the proposed algorithm, the pedestrian is equipped with an inertial measurement unit attached to the waist, which provides three-axis accelerometer and gyroscope signals. The main goal is to integrate the activity classification and step-length estimation algorithms into a PDR system. In order to improve the step-length estimation, several types of activities are classified using a multi-layer perceptron (MLP) neural network with feature extraction based on statistical parameters from wavelet decomposition. This work focuses on classifying activities that a pedestrian performs routinely in his daily life, such as walking, walking fast, jogging and running. The step-length is dynamically estimated using a multiple-input–single-output (MISO) fuzzy inference system. Results provide an average classification rate of 87.49 % with an accuracy on step-length estimation about 92.57 % in average.

Mariana Natalia Ibarra-Bonilla, Ponciano Jorge Escamilla-Ambrosio, Juan Manuel Ramirez-Cortes, Jose Rangel-Magdaleno, Pilar Gomez-Gil

Geo-Navigation for a Mobile Robot and Obstacle Avoidance Using Fuzzy Controllers

This chapter presents the design of a system of fuzzy controllers for a differential mobile robot that was developed to navigate in outdoors environments over a predetermined route from point A to point B without human intervention. The mobile robot has the main features of geo-navigation to obtain its current position during the navigation, obstacles detection and the avoidance of these obstacles in an autonomous form. In this work to achieve the autonomous navigation in real-time, it was necessary to design a system based on fuzzy controllers. The system performs the detection and the analysis of the surrounding environment of the mobile robot to take actions that allow achieving the target point in a safe way. The position and orientation of the mobile robot is achieved with the use of geographical coordinates, through a GPS and the use of a magnetic compass which determines the steering angle. The detection of the environment is through ultrasonic sensors mounted on the mobile robot. All the inputs are taken by the system to compute through fuzzy rules the motion control of the mobile robot, to estimate the position and orientation accurately and to control the speed of the two DC motors to drive the wheels. In this work, the experiments were performed in dynamic outdoors environments, where the mobile robot performed successfully the navigation and the obstacles avoidance. In all the experiments, the mobile robot achieved its mission to reach the target position without human intervention; the results show the validity of the developed system. The experimental framework, experiments and results are explained in terms of performance and accuracy.

Oscar Montiel, Roberto Sepúlveda, Ignacio Murcio, Ulises Orozco-Rosas

Ad Text Optimization Using Interactive Evolutionary Computation Techniques

The description of a product or an ad’s text can be rewritten in many ways if other text fragments similar in meaning substitute different words or phrases. A good selection of words or phrases, composing an ad, is very important for the creation of an advertisement text, as the meaning of the text depends on this and it affects in a positive or a negative way the interest of the possible consumers towards the advertised product. In this chapter we present a method for the optimization of advertisement texts through the use of interactive evolutionary computing techniques. The EvoSpace platform is used to perform the evolution of a text, resulting in an optimized text, which should have a better impact on its readers in terms of persuasion.

Quetzali Madera, Mario García-Valdez, Alejandra Mancilla

Using Semantic Representations to Facilitate the Domain-Knowledge Portability of a Natural Language Interface to Databases

Our research is focused on the implementation of a Natural Language Interface to Database. We propose the use of ontologies to model the knowledge required by the interface with the aim of correctly answering natural language queries and facilitate its configuration on other databases. The knowledge of our interface is composed by modeling information about the database schema, its relationship to natural language and some linguistic functions. The design of this modeling allows users to configure the interface without performing complex and tedious tasks, facilitating its portability to other databases. To evaluate the knowledge-domain portability, we configured our interface and the commercial interface ELF in the Northwind database. The results obtained of the experimentation show that the knowledge modeled in our interface allowed it to achieve a good performance.

Juan J. González B, Rogelio Florencia-Juárez, Rodolfo A. Pazos Rangel, José A. Martínez F, María L. Morales-Rodríguez

Post-Filtering for a Restaurant Context-Aware Recommender System

Nowadays recommender systems are successfully used in various fields. One application is the recommendation of restaurants, where even if the method of customer service is the same, the quality of service varies depending on the resources invested to improve it. Traditionally, in a restaurant a waiter takes orders from customers and then delivers the product. The motivation of this work is to make recommendations of restaurants with the aim of disseminating information about products and services offered by restaurants in the city of Tijuana through a Web based platform. The proposed recommendation algorithm is based on contextual post-filtering approach, using the output of a collaborative filtering algorithm together with contextual information of the user’s current situation. The dataset used was explicitly acquired through questionnaires answered by 50 users; and the experiment was performed with a data set of 1,422 ratings of 50 users and 40 restaurants. We evaluate our approach with Mean Absolute Error (MAE) using dataset obtained of the questionnaire and the experimental results show that our approach has an acceptable accuracy for the dataset used.

Xochilt Ramirez-Garcia, Mario García-Valdez

Design of Fuzzy Controllers for a Hexapod Robot

The legged robots have emerged by the necessity of vehicles capable of travel and access safely on natural or unstructured terrains, in which vehicles with traditional travel systems (like the wheels) are unable to access, or if they achieve, they move on them with very low efficiency. However, despite the advantages of mobile robots with legs, there are limitations that hinder its use like the control of movement of their legs, the algorithm of locomotion, trajectory tracking and the obstacle avoidance. In our days, a very useful alternative applied to control systems is fuzzy logic; this one is capable of modeling mathematical complex systems. Therefore, fuzzy logic has been becoming popular in control systems for complex and nonlinear plants. The aim of this work is to make algorithms to control the hexapod robot body. The development of these algorithms uses fuzzy logic techniques for controlling the servomotors of the robot. Matlab algorithms are performed to establish a wireless communication using the ZigBee communication protocol, and we use the genetic algorithm toolbox from Matlab to make the control of the hexapod robot body in the “x–y” plane, this is a multi-objective optimization problem due to the stabilization of the robot body in “x” and the stabilization of the robot body in “y”.

Roberto Sepúlveda, Oscar Montiel, Rodolfo Reyes, Josué Domínguez
Weitere Informationen

Premium Partner

    Bildnachweise