Computação Bioinspirada

Nesta disciplina trabalharemos com métodos computacionais.

Estudaremos estratégias para resolver problemas.

Estas estratégias são fartamente discutidas na literatura, e tem em comum o fato de que todas possuem forte inspiração em algum modelo da Biologia.

A disciplina será desenvolvida no formato paper-driven. Isso significa que vocês terão que ler, resumir e apresentar artigos.

Teremos um total de 5 estratégias diferentes a serem estudadas.

        1. Redes Neurais

        2. Algoritmos Genéticos

        3. Colônia de Formigas

        4. Enxame de Partículas

        5. Sistema Imunológico Natural

Naturalmente este conjunto pode aumentar, caso alguém apareça com uma sugestão interessante.

Apresentações

1. Apresentação - Apresentacao.odp

2. Introdução - Introducao.odp

3. Complexidade de Algoritmos (revisão) - ComplexidadeAlgoritmos.odp

4. Introdução às Redes Neurais - RedesNeurais.odp

5. Algoritmos Genéticos - AlgoritmosGeneticos.odp

6. Colônia de Formigas - ColoniaFormigas.odp

7. Enxame de Partículas - EnxameParticulas.odp

8. Sistemas Imunológicos Naturais - Imunologicos.odp

Escolhendo os papers para apresentar

Cada aluno apresentará pelo menos um artigo. E todos os alunos devem ler e resumir todos os artigos.

O apresentador do paper, naturalmente, pertence ao conjunto "todos".

Leia aqui algumas palavras sobre a organização de artigos científicos. Isso deve ajudá-lo a ler.

Atenção! O Primeiro paper já está disponível aqui!

Lista de Papers (resumida)

Algoitmos Genéticos

Multilevel thresholding for segmentation of medical brain images using real coded genetic algorithm

Medical image analysis is one of the major research areas in the last four decades. Many researchers have contributed quite good algorithms and reported results. In this paper, real coded genetic algorithm with Simulated Binary Crossover (SBX) based multilevel thresholding is used for the segmentation of medical brain images. The T2 weighted Magnetic Resonance Imaging (MRI) brain images are considered for image segmentation. The optimum multilevel thresholding is found by maximizing the entropy. The results are compared with the results of the existing algorithms like Nelder–Mead simplex, PSO, BF and ABF. The statistical performances of the 100 independent runs are reported. The results reveal that the performance of real coded genetic algorithm with SBX crossover based optimal multilevel thresholding for medical image is better and has consistent performance than already reported methods.

Genetics_MultiLevelTrheshold

-------------------------------------------------

A genetic algorithm for multiprocessor scheduling

The problem of multiprocessor scheduling can be stated as finding a schedule for a general task graph to be executed on a multiprocessor system so that the schedule length can be minimized. This scheduling problem is known to be NP-hard, and methods based on heuristic search have been proposed to obtain optimal and suboptimal solutions. Genetic algorithms have recently received much attention as a class of robust stochastic search algorithms for various optimization problems. In this paper, an efficient method based on genetic algorithms is developed to solve the multiprocessor scheduling problem. The representation of the search node is based on the order of the tasks being executed in each individual processor. The genetic operator proposed is based on the precedence relations between the tasks in the task graph. Simulation results comparing the proposed genetic algorithm, the list scheduling algorithm, and the optimal schedule using random task graphs, and a robot inverse dynamics computational task graph are presented

Genetics_MultiprocessorScheduling

------------------------------------------------

A genetic algorithm for the vehicle routing problem

This study considers the application of a genetic algorithm (GA) to the basic vehicle routing problem (VRP), in which customers of known demand are supplied from a single depot. Vehicles are subject to a weight limit and, in some cases, to a limit on the distance travelled. Only one vehicle is allowed to supply each customer.

The best known results for benchmark VRPs have been obtained using tabu search or simulated annealing. GAs have seen widespread application to various combinatorial optimisation problems, including certain types of vehicle routing problem, especially where time windows are included. However, they do not appear to have made a great impact so far on the VRP as described here. In this paper, computational results are given for the pure GA which is put forward. Further results are given using a hybrid of this GA with neighbourhood search methods, showing that this approach is competitive with tabu search and simulated annealing in terms of solution time and quality.

Scope and purpose

The basic vehicle routing problem (VRP) consists of a number of customers, each requiring a specified weight of goods to be delivered. Vehicles despatched from a single depot must deliver the goods required, then return to the depot. Each vehicle can carry a limited weight and may also be restricted in the total distance it can travel. Only one vehicle is allowed to visit each customer. The problem is to find a set of delivery routes satisfying these requirements and giving minimal total cost. In practice, this is often taken to be equivalent to minimising the total distance travelled, or to minimising the number of vehicles used and then minimising total distance for this number of vehicles.

Most published research for the VRP has focused on the development of heuristics. Although the development of modern heuristics has led to considerable progress, the quest for improved performance continues. Genetic algorithms (GAs) have been used to tackle many combinatorial problems, including certain types of vehicle routing problem. However, it appears that GAs have not yet made a great impact on the VRP as described here. This paper describes a GA that we have developed for the VRP, showing that this approach can be competitive with other modern heuristic techniques in terms of solution time and quality.

Genetics_VehicleRouting

---------------------------------------------

An Implementation of Intrusion Detection System Using Genetic Algorithm

Nowadays it is very important to maintain a high level security to ensure safe and trusted communication of information between various organizations. But secured data communication over internet and any other network is always under threat of intrusions and misuses. So Intrusion Detection Systems have become a needful component in terms of computer and network security. There are various approaches being utilized in intrusion detections, but unfortunately any of the systems so far is not completely flawless. So, the quest of betterment continues. In this progression, here we present an Intrusion Detection System (IDS), by applying genetic algorithm (GA) to efficiently detect various types of network intrusions. Parameters and evolution processes for GA are discussed in details and implemented. This approach uses evolution theory to information evolution in order to filter the traffic data and thus reduce the complexity. To implement and measure the performance of our system we used the KDD99 benchmark dataset and obtained reasonable detection rate.

Genetics_IntrusionDetection

-------------------------------------------

Redes Neurais Artificiais

Predicting criminal recidivism using neural networks

Prediction of criminal recidivism has been extensively studied in criminology with a variety of statistical models. This article proposes the use of neural network (NN) models to address the problem of splitting the population into two groups — non-recidivists and eventual recidivists — based on a set of predictor variables. The results from an empirical study of the classification capabilities of NN on a well-known recidivism data set are presented and discussed in comparison with logistic regression. Analysis indicates that NN models are competitive with, and may offer some advantages over, traditional statistical models in this domain.

Neural_PredictingCrime

---------------------------------------------

Short Term Traffic Flow Prediction for a Non Urban Highway Using Artificial Neural Network

This study applies Artificial Neural Network (ANN) for short term prediction of traffic flow using past traffic data. The model incorporates traffic volume, speed, density, time and day of week as input variables. Speed of each category of vehicles was considered separately as input variables in contrast to previous studies reported in literature which consider average speed of combined traffic flow. Results show that Artificial Neural Network has consistent performance even if time interval for traffic flow prediction was increased from 5 minutes to 15 minutes and produced good results even though speeds of each category of vehicles were considered separately as input variables.

Neural_TrafficFlowPrediction

---------------------------------------------

Portfolio selection using neural networks

In this paper we apply a heuristic method based on artificial neural networks (NN) in order to trace out the efficient frontier associated to the portfolio selection problem. We consider a generalization of the standard Markowitz mean-variance model which includes cardinality and bounding constraints. These constraints ensure the investment in a given number of different assets and limit the amount of capital to be invested in each asset. We present some experimental results obtained with the NN heuristic and we compare them to those obtained with three previous heuristic methods. The portfolio selection problem is an instance from the family of quadratic programming problems when the standard Markowitz mean-variance model is considered. But if this model is generalized to include cardinality and bounding constraints, then the portfolio selection problem becomes a mixed quadratic and integer programming problem. When considering the latter model, there is not any exact algorithm able to solve the portfolio selection problem in an efficient way. The use of heuristic algorithms in this case is imperative. In the past some heuristic methods based mainly on evolutionary algorithms, tabu search and simulated annealing have been developed. The purpose of this paper is to consider a particular neural network (NN) model, the Hopfield network, which has been used to solve some other optimisation problems and apply it here to the portfolio selection problem, comparing the new results to those obtained with previous heuristic algorithms.

Neural_Portfolio

---------------------------------------------------------

An Efficient Weather Forecasting System using Artificial Neural Network

Temperature warnings are important forecasts because they are used to protect life and property. Temperature forecasting is the application of science and technology to predict the state of the temperature for a future time and a given location. Temperature forecasts are made by collecting quantitative data about the current state of the atmosphere. In this paper, a neural network-based algorithm for predicting the temperature is presented. The Neural Networks package supports different types of training or learning algorithms. One such algorithm is Back Propagation Neural Network (BPN) technique. The main advantage of the BPN neural network method is that it can fairly approximate a large class of functions. This method is more efficient than numerical differentiation. The simple meaning of this term is that our model has potential to capture the complex relationships between many factors that contribute to certain temperature. The proposed idea is tested using the real time dataset. The results are compared with practical working of meteorological department and these results confirm that our model have the potential for successful application to temperature forecasting. Real time processing of weather data indicate that the BPN based weather forecast have shown improvement not only over guidance forecasts from numerical models, but over official local weather service forecasts as well.

Neural_WeatherForecasting

--------------------------------------------------------

Colônia de Formigas

An Ant Colony Algorithm for efficient ship routing

With the substantial rising of international oil price and global warming on the rise, how to reduce

operational fuel consumption and decrease air pollution has become one of the pursued goals of green

ship. Ship route planning is an indispensible part of the ship navigation process, especially in transoceanic

crossing ship routing. The soundness of ship routing not only affects the safety of ship navigation but also

the operation economy and environmental protection. This research is based on the platform of Electronic

Chart Display and Information System (ECDIS), and founded on Ant Colony Algorithm (ACA) combined

with the concept of Genetic Algorithm (GA), to model living organisms optimization behaviour to perform

efficient ship route planning in transoceanic crossing. Besides the realization of route planning automation,

ship routing will achieve the goal of optimum carbon dioxide reduction and energy conservation, and

provide reference for route planning decision.

AntColony_ShipRoute

------------------------------------------------------

Ant colony optimization for real-world vehicle routing problems

 Ant colony optimization (ACO) is a metaheuristic for combinatorial optimization problems. In this paper we report on its successful application to the vehicle routing problem (VRP). First, we introduce the VRP and some of its variants, such as the VRP with time windows, the time dependent VRP, the VRP with pickup and delivery, and the dynamic VRP. These variants have been formulated in order to bring the VRP closer to the kind of situations encountered in the real-world.

Then, we introduce the basic principles of ant colony optimization, and we briefly present its application to the solution of the VRP and of its variants.

Last, we discuss the applications of ACO to a number of real-world problems: a VRP with time windows for a major supermarket chain in Switzerland; a VRP with pickup and delivery for a leading distribution company in Italy; a time dependent VRP for freight distribution in the city of Padua, Italy, where the travel times depend on the time of the day; and an on-line VRP in the city of Lugano, Switzerland, where customers’ orders arrive during the delivery process.

AntColony_RealVehicleRoute

----------------------------------------------------

Computer network load-balancing and routing by ant colony optimization

A high efficient design of computer network is an important issue for the high transmission speed requirement of today. In computer network, the data packages have to be transmitted to the destination with a minimum delay for ensuring the quality of service guarantees. This work presents an algorithm to perform a dynamic load-balancing for transmitting the data packages with near minimum delays in the interconnection networks. The proposed algorithm is based on the ant colony optimization algorithm inspired by the simple behavior of biological ants. This work utilizes a cube topology network to evaluate the performance of the proposed algorithm. From the comparing results, the proposed algorithm can achieve good network utilization by the low rate of the bandwidth blocking.

AntColony_RouteLoadBalanceNetworks

----------------------------------------------------

Enxame de Partículas

Optimal power flow using particle swarm optimization

This paper presents an efficient and reliable evolutionary-based approach to solve the optimal power flow (OPF) problem. The proposed approach employs particle swarm optimization (PSO) algorithm for optimal settings of OPF problem control variables. Incorporation of PSO as a derivative-free optimization technique in solving OPF problem significantly relieves the assumptions imposed on the optimized objective functions. The proposed approach has been examined and tested on the standard IEEE 30-bus test system with different objectives that reflect fuel cost minimization, voltage profile improvement, and voltage stability enhancement. The proposed approach results have been compared to those that reported in the literature recently. The results are promising and show the effectiveness and robustness of the proposed approach.

ParticleSwarm_PowerFlow.pdf

----------------------------------------------------

Particle Swarm Optimization for the Vehicle Routing Problem with Stochastic Demands

This paper introduces a new hybrid algorithmic approach based on Particle Swarm Optimization (PSO) for successfully solving one of the most popular supply chain management problems, the Vehicle Routing Problem with Stochastic Demands (VRPSD). The VRPSD is a well known NP-hard problem in which a vehicle with finite capacity leaves from the depot with full load and has to serve a set of customers whose demands are known only when the vehicle arrives to them. A number of different variants of the PSO are tested and the one that performs better is used for solving benchmark instances from the literature.

ParticleSwarm_VehicleRoute.pdf

--------------------------------------------------------

Flight Conflict Resolution for Civil Aviation Based on Ant Colony Optimization

More and more congestions are emerging because of the increasing of air traffic flow in china. in order to facilitate civil-aviation traffic, a flight conflict resolution method based on ACO (Ant Colony Optimization) is surveyed in this paper. the optimization objective function which not only includes trajectory length factor but also passengers comfort factor is constructed. an ACO model for flight conflict resolution is established. the experimental results show that the optimized trajectory achieved by ACO is better than those obtained by GA and PSO.

ParticleSwarm_FlightConflict.pdf

---------------------------------------------------------

Sistemas Imunológicos Artificiais

A novel model for credit card fraud detection using Artificial Immune Systems

The amount of online transactions is growing these days to a large number. A big portion of these transactions contains credit card transactions. The growth of online fraud, on the other hand, is notable, which is generally a result of ease of access to edge technology for everyone. There has been research done on many models and methods for credit card fraud prevention and detection. Artificial Immune Systems is one of them. However, organizations need accuracy along with speed in the fraud detection systems, which is not completely gained yet. In this paper we address credit card fraud detection using Artificial Immune Systems (AIS), and introduce a new model called AIS-based Fraud Detection Model (AFDM). We will use an immune system inspired algorithm (AIRS) and improve it for fraud detection. We increase the accuracy up to 25%, reduce the cost up to 85%, and decrease system response time up to 40% compared to the base algorithm.

ArtificialImmune_CreditCardFraud.pdf

----------------------------------------------------------

Immune system approaches to intrusion detection – a review

The use of artificial immune systems in intrusion detection is an appealing concept for two reasons. First, the human immune system provides the human body with a high level of protection from invading pathogens, in a robust, self-organised and distributed manner. Second, current techniques used in computer security are not able to cope with the dynamic and increasingly complex nature of computer systems and their security. It is hoped that biologically inspired approaches in this area, including the use of immune-based systems will be able to meet this challenge. Here we review the algorithms used, the development of the systems and the outcome of their implementation. We provide an introduction and analysis of the key developments within this field, in addition to making suggestions for future research.

ArtificialImmune_IntrusionDetection.pdf

------------------------------------------------------------

Artificial Immune Systems applied to the reconfiguration of electrical power distribution networks for energy loss minimization

This paper presents a methodology for the reconfiguration of radial electrical distribution systems based on the bio-inspired meta-heuristic Artificial Immune System to minimize energy losses. The proposed approach can handle this combinatorial mixed integer problem of nonlinear programming. Radiality and connectivity constraints are considered as well as different load levels for planning the system operation. For this purpose, improvements to an algorithm in the literature are proposed to better accommodate the features of the problem and to improve the search process. The algorithm developed is tested in well-known distribution systems.

ArtificialImmune_ElectricalPowerReconfig

Datas e responsabilidades das das apresentações