Introduction to Neural Networks for Java, Session 5
| Course Name | Introduction to Neural Networks for Java |
| Instructor | jeffheaton |
| Session Title | Genetic Algorithms, Traveling Salesman, TicTacToe |
| Session Number | 5 |
Session Material
Backpropagation is not the only way to train a feedforward neural network. Neural networks. There are many training algorithms for this purpose. This course will focus on backpropagation, genetic training and simulated annealing. This class session will focus on genetic training. Genetic training uses a genetic algorithm.
You might wonder why you would need more than one training algorithm. Sometimes a neural network will not train effectively with a particular training algorithm. Some problems will require multiple training algorithms. Such hybrid solutions can often find a solution faster than a single solution.
How a Genetic Algorithm Works
Genetic algorithms attempt to solve computer problems by simulating the way that organisms evolve into new organifimsms that are better suited to their environment. A genetic algorithm evolves potential solutions.
To use a genetic algorithm the solution must be broken down into an array of numbers. Further, this array of numbers must always be the same length. This string of numbers corresponds to a DNA double helix. As the organisms mate with each other, this DNA strand will be split and recombined. This allows offspring to inherit desirable traits from their parents.
Different texts will define the parts of a genetic algorithm differently. This course uses the following terms.
- Gene - One number in the DNA sequence
- Chromosome - One DNA sequence
- Life-form - One or more chromosomes
This is a very simplified version of what is really going on in biology. In this course the life-forms will always have a single chromosome.
Mutation is also used. Sometimes the elements to an optimal solution may not be present in the population pool. Mutation allows the genes to be randomized a bit to introduce new traits. Mutation introduces new traits in biological systems as well.
The Traveling Salesman Problem
The traveling salesman problem has long been a mainstay for computer science. A salesman must visit an itinerary of cities. But, what is the optimal route through these cities? Traditional brute force programming can solve this problem for a small number of cities. However, larger number of cities require less traditional programming, for example, a genetic algorithm.
To adapt the traveling salesman problem (TSP) to a genetic algorithm the optimal solutions must be converted to chromosomes. This is relatively easy for the TSP. Each potential solution is an itinerary. The itinerary can be converted to a chromosome by simply creating an array that contains the cities to be visited, in the order to visit them.
Training a Neural Network
Adapting a neural network to a genetic algorithm is relativly easy as well. The weight and threshold matrix is simply converted to a long string of floating point values.
Programming Assignment #1
The following programming assignment is due by the next class session. We will review this programming assignment in the next class session.
Learning Objectives:
- Learn to read data from CSV files
- Train a neural network for multiple patterns
- Create a feedforward neural network
The XOR example that we saw earlier simply hard coded all of the XOR training data into the program. This is okay for small data sets that will never change, however, the other programming assignments in this course will require larger training sets than you would like to hard code into a program. Program 1 shows you how to read CSV files.
Shown here is a CSV file for the XOR operator:
Listing: A CSV File for the XOR Operator
0,0,0 0,1,1 1,0,1 1,1,0
The following program demonstrates how to read a CSV file using the ReadCSV class. This is an enhanced version of the ReadCSV class that was provided by the book.
Listing: Reading a CSV File
package com.heatonresearch.course.introneuralnet.csvtest;
import java.io.IOException;
import com.heatonresearch.book.introneuralnet.common.ReadCSV;
public class CSVTest {
public static void main(String args[])
{
try {
ReadCSV csv = new ReadCSV("c:\\data\\xor.csv",false);
while(csv.next())
{
double in1 = Double.parseDouble(csv.get(0));
double in2 = Double.parseDouble(csv.get(1));
double out1 = Double.parseDouble(csv.get(2));
System.out.println("Input 1:"+in1);
System.out.println("Input 2:"+in2);
System.out.println("Output 1:"+out1);
System.out.println("-------------");
}
} catch (Throwable e) {
e.printStackTrace();
}
}
}
This program produces the following output.
Listing: Program Output
Input 1:0.0 Input 2:0.0 Output 1:0.0 ------------- Input 1:0.0 Input 2:1.0 Output 1:1.0 ------------- Input 1:1.0 Input 2:0.0 Output 1:1.0 ------------- Input 1:1.0 Input 2:1.0 Output 1:0.0 -------------
The ReadCSV class provided by the book always assumes that the first line of the CSV file contains the column header names. This is not always the case. As a result, the enhanced version of the ReadCSV class provides a boolean field on the constructor that specifies if the header line is present. You can see the enhanced ReadCSV here.
Listing: Enhanced ReadCSV.java
/**
* Introduction to Neural Networks with Java, 2nd Edition
* Copyright 2008 by Heaton Research, Inc.
* http://www.heatonresearch.com/books/java-neural-2/
*
* ISBN13: 978-1-60439-008-7
* ISBN: 1-60439-008-5
*
* This class is released under the:
* GNU Lesser General Public License (LGPL)
* http://www.gnu.org/copyleft/lesser.html
*/
package com.heatonresearch.book.introneuralnet.common;
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.text.DateFormat;
import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.Date;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
/**
* ReadCSV: Read and parse CSV format files.
*
* @author Jeff Heaton
* @version 2.1
*/
public class ReadCSV {
private static final DateFormat sdf = new SimpleDateFormat("yyyy-MM-dd");
public static String displayDate(final Date date) {
return sdf.format(date);
}
public static Date parseDate(final String when) {
try {
return sdf.parse(when);
} catch (final ParseException e) {
return null;
}
}
private final BufferedReader reader;
private final Map<String, Integer> columns = new HashMap String, Integer>();
private String data[];
public ReadCSV(final String filename, boolean headers) throws IOException {
this.reader = new BufferedReader(new FileReader(filename));
if( headers) {
// read the column heads
final String line = this.reader.readLine();
final StringTokenizer tok = new StringTokenizer(line, ",");
int i = 0;
while (tok.hasMoreTokens()) {
final String header = tok.nextToken();
this.columns.put(header.toLowerCase(), i++);
}
this.data = new String[i];
}
}
public void close() throws IOException {
this.reader.close();
}
public String get(final int i) {
return this.data[i];
}
public String get(final String column) {
final Integer i = this.columns.get(column.toLowerCase());
if (i == null) {
return null;
}
return this.data[i.intValue()];
}
public Date getDate(final String column) throws ParseException {
final String str = get(column);
return sdf.parse(str);
}
public double getDouble(final String column) {
final String str = get(column);
return Double.parseDouble(str);
}
public int getInt(final String col) {
final String str = get(col);
try {
return Integer.parseInt(str);
} catch (final NumberFormatException e) {
return 0;
}
}
public boolean next() throws IOException {
final String line = this.reader.readLine();
if (line == null) {
return false;
}
StringTokenizer tok = new StringTokenizer(line, ",");
if( this.data==null ) {
int len = 0;
while(tok.hasMoreTokens() )
{
len++;
tok.nextToken();
}
this.data = new String[len];
tok = new StringTokenizer(line, ",");
}
int i = 0;
while (tok.hasMoreTokens()) {
final String str = tok.nextToken();
if (i < this.data.length) {
this.data[i++] = str;
}
}
return true;
}
}
For this programming assignment you must create a CSV file. Then read it to the input and ideal arrays for training. You should construct a CSV file that will train the network for the XOR, AND and OR operators. Because these are three different operators you will need some way of communicating to the neural network WHICH operator it is attempting to process. To do this, it is suggested that the neural network be constructed as follows:
- Input 1: The left side of the operation
- Input 2: The right side of the operation
- Input 3: Is this an XOR operation? (1=yes, 0=otherwise)
- Input 4: Is this an AND operation? (1=yes, 0=otherwise)
- Input 5: Is this an OR operation? (1=yes, 0=otherwise)
- Output 1: The output from this operation
Find a suitable number of hidden layer neurons.
Example. The input for "true and false" would be:
1,0,0,1,0
To submit this program send a ZIP with both the CSV and source file(s) to the "support" email address at the website heatonresearch.com.
I have provided a starting point Eclipse project file for this assignment. You can download all of the book files and a simple XOR example. This includes the extended ReadCSV class. Simply create a new package in this project to create your assignment. You need only submit your source file(s) and CSV.
[Download Class Starting Project]
RSS
YouTube
Twitter
Facebook
