Soft Computing

Soft Computing covers a wide array of techniques which seek inspiration in natural phenomena in order to extract heuristics. A heuristic can be defined as a general guideline to solving a problem. These heuristics are applied to very hard or impossible problems to solve with more formal, conventional methods. The obtained solutions might not be optimal, but they are usually good approximations. Some heuristics will be described in order to provide examples. Links to Java Applets will be provided for further understanding, hoping that the graphical demonstrations will be useful.

 

Artificial Neural Networks 

annlogo.pngAlthough the first computers where dubbed "electronic brains", biological nervous systems take a radically different approach to perform their tasks. While computers are devices designed to strictly follow lists of unambiguous instructions, neural networks are massively parallel systems intended to implement pattern-matching responses and store knowledge and data. Making abstractions over the real, biological neuron, artificial neural networks (ANNs) are a well-established tool to solving many kinds of problems and it is also an active field of research.

If you want to know more, a good starting point is the Wikipedia article. Many Java Applets using ANNs are scattered through the web, but they show either the underlying ANN or their results, as seeing the net in action is often meaningless. We will give two examples:

  •  In the first one, a perceptron (the simplest ANN) with only a neuron is shown. It can be trained to learn most binary functions.
  •  In the second one, a most advanced network (the Kohonen Map) is used to solve the travelling salesman problem. The neurons are arranged in a ring, and they try to adapt it to an optimal route through a set of cities.

 

 

Genetic Algorithms

galogo.jpgNatural selection seems to have performed well, since organisms are very well adapted to solving the problem of survival. This idea inspired John Holland to try to solve computational problems in a similar way.  To solve a problem, a population of initial solutions is built up. Each solution has got a fitness value measuring how good it is. Solutions with higher fitness are allowed to reproduce more often than worse ones. The reproduction process involves mixing good solutions (crossover), and occasionally introducing variations (mutation). A very good java applet shows graphically an example.

 

 

Ant Colony Optimization

acologo.pngAn ant colony has no centralized direction, and ants themselves are rather stupid insects, but the colony is able to organize its workers to find optimal routes from the nests to the food. A heuristic to solve problems (mainly by means of constructing the solution step by step) has been developed based on the behaviour of ants. The algorithm has a number of artificial ants which swarm over the solutions, each ant influencing over the decisions of the other. In this java applet , the travelling salesman problem is solved: each ant tries to visit the cities in the smallest possible distance. Good sub-paths are preferentially roamed, and finally all the ants converge onto a good path.

 

  

Particle Swarm Optimization

psologo.pngThis heuristic draws inspiration from social networks. People solve problems by talking with others, exchanging information about possible ways to find the solution. To solve a problem, this heuristic uses a population of agents (particles). Each particle moves from one solution to another. Particles take into account of how good other agents perform, and change their trajectory over possible solutions according to this information. Eventually, the individuals of the particle swarm converge over a consensus solution. A good graphical demonstration can be seen here.

 

 

Fuzzy Logic

fuzzylogo.pngMathematicians rejoice in the world of bare truths provided by formal logic, but the fact is that these formalisms do not fit well in the real world. Fuzzy logic is a mathematical tool to express degrees of truth, and to manipulate propositions with varying degrees of truth. For example, the statement "in Málaga, 01/01/2008 was sunny" can be true within a range of degrees: the whole sky was blue, or maybe there were slightly, high-altitude clouds? It has many practical applications; in fact, fuzzy logic control is thriving among washing machines and refrigerators. A very apparent demonstration is an applet showing a fuzzy-controlled shower. Another applet example is a fuzzy-controlled fan , which shows the internal workings of the fuzzy driver.

 

 

Bayesian Networks

bayelogo.pngAnother aspect which formal logic has a hard time modelling is probability about facts.Bayesian Networks are a tool to construct formal reasoning involving probabilities, generating networks of logically-linked concepts which can predict the probabilities of the modelled events whenever our knowledge of the situation changes.  They are widely used to model human knowledge in many fields. For example, given a number of symptoms, a Bayesian network can predict probabilities of several diseases. There are many commercial and open-source Bayesian tools; this is just one.