Showing posts with label Open Source. Show all posts

Wednesday, June 28, 2017

C++ implementation for Linear Genetic Programming

cpp-linear-genetic-programming

https://github.com/chen0040/cpp-linear-genetic-programming

Package provides C++ implementation of linear genetic programming algorithms described in the book "Linear Genetic Programming".

Introduction

Linear Genetic Programming examines the evolution of imperative computer programs written as linear sequences of instructions. In contrast to functional expressions or syntax trees used in traditional Genetic Programming (GP), Linear Genetic Programming (LGP) employs a linear program structure as genetic material whose primary characteristics are exploited to achieve acceleration of both execution time and evolutionary progress (From the book "Linear Genetic Programming").

Usage

git clone this project to your local computer. The solution file can be open and run using Visual Studio IDE 2017.

Please refers one of the following folders (each of which solve a different optimization problem) on how to create the set of source files that will solve your problem:

mexican_hat
spiral_classification
symreg

The main code to run in the main looks like the following (Note that the C++ code uses xml files for configuration), you can test run the codes in the main.cpp file.

void mexican_hat_demo()
{
 LGPConfig config("mexican_hat\\LGPConfig.xml");
 std::cout << config.ToString() << std::endl;

 mexican_hat::XPop  pop(&config);
 //LGPStats stats(&pop);

 pop.BreedInitialPopulation();

 while(!pop.Terminated())
 {
  pop.Evolve();
  std::cout << "mexican hat generation: " << pop.GetCurrentGeneration() << std::endl;
  std::cout << "global fitness: " << pop.GetGlobalFittestProgram()->GetFitness() << "\tcurrent fitness: " << pop.GetFittestProgram()->GetFitness() << std::endl;
  //stats.LogStatistics();
 }

 std::cout << pop.GetGlobalFittestProgram()->ToString(true) << std::endl;
}

C# codes for working with powerpoint

cs-vsto-powerpoint-writer

https://github.com/chen0040/cs-vsto-powerpoint-writer

Package provides VSTO-based C# implementation of a powerpoint modifier

Objective

The project is to create a simple library which uses VSTO to automate powerpoint modification by using C# DSL syntax.

Langauage

Install

The library was built using VS2015 Community Edition. You can clone and build the library then add the library to your references in a .NET project. Note that this library is based on VSTO and thus requires the availability of office 2007 for it to work. It also requires the following COM libraries to be available in the C# project's references

Microsoft.Office.Core (Version: 2.4)
Microsoft.Office.Interop.Excel (Version: 1.6)
Microsoft.Office.Interop.Powerpoint (Version: 2.9)

This link below shows how to solve the COM error when uninstall vs 2007 and reinstall some other version of office and then reinstall vs 2007:

https://social.msdn.microsoft.com/Forums/vstudio/en-US/08f13e9d-895c-4102-b6d9-e327af8cf8c0/0x80029c4a-typeecantloadlibrary?forum=vsto

Usage

Below is the C# sample code for modifying the input.ppt and producing the output.ppt:

PowerPointReportModifier builder = new PowerPointReportModifier();
builder.ChartIntercepted += (sender, e) =>
{
 string title = e.Title;
 PowerPoint.Chart chart = e.Chart;
 Worksheet sheet = e.Worksheet;

 // code to modify the chart here
};
builder.TableIntercepted += (sender, e) =>
{
 PowerPoint.Table table = e.Table;

 // code to modify the table here
};
builder.TextFrameIntercepted += (sender, e) =>
{
 PowerPoint.TextRange paragraph = e.Paragraph;
 
 // code to modify the paragraph here
};

builder.Apply("input.ppt", "output.ppt");

Text compression in Python

pycompressor

https://github.com/chen0040/pycompressor

Package provides python implementation of string compressor

https://travis-ci.org/chen0040/pycompressor.svg?branch=master

https://coveralls.io/repos/github/chen0040/pycompressor/badge.svg?branch=master

https://scrutinizer-ci.com/g/chen0040/pycompressor/badges/quality-score.png?b=master

Install

Run the following command to install pycompressor using pip

$ pip install pycompressor

Usage:

from pycompressor.huffman import HuffmanCompressor
huffman = HuffmanCompressor()
original = 'Lorem Ipsum is simply dummy text of the printing and typesetting industry. Lorem Ipsum has been the industry\'s standard dummy text ever since the 1500s, when an unknown printer took a galley of type and scrambled it to make a type specimen book. It has survived not only five centuries, but also the leap into electronic typesetting, remaining essentially unchanged. It was popularised in the 1960s with the release of Letraset sheets containing Lorem Ipsum passages, and more recently with desktop publishing software like Aldus PageMaker including versions of Lorem Ipsum.'
print('before compression: ' + original)
print('length: ' + str(len(original)))
compressed = huffman.compress_to_string(original)
print('after compression: ' + compressed)
print('length: ' + str(len(compressed)))
decompressed = huffman.decompress_from_string(compressed)
print('after decompression: ' + decompressed)
print('length: ' + str(len(decompressed)))

Recommender engine in Spark

spark-ml-recommender

https://github.com/chen0040/spark-ml-recommender

Package provides java implementation of big-data recommend-er using Apache Spark

Feature

Collaborative filtering recommender that predicts user's preference on unknown items using ALS-based gradient descent
Recommender that computes the correlation / similarity between items based on user preference using Pearson / Cosine / Jaccard correlation coefficient
Recommender that recommends a common friend to connect two persons who do not know each other but like to know each other (something similar to linkedIn connection)

Install

Add the following dependency to your POM file:

<dependency>
  <groupId>com.github.chen0040</groupId>
  <artifactId>spark-ml-recommender</artifactId>
  <version>1.0.4</version>
</dependency>

Usage

Predict missing ratings

The sample code below tries to predict the missing rating of [user, movie] as shown in the ratingTable below:

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");

RatingTable ratingTable =new RatingTable();
ratingTable.addRating("Love at last", "Alice", 5);
ratingTable.addRating("Remance forever", "Alice", 5);
ratingTable.addRating("Nonstop car chases", "Alice", 0);
ratingTable.addRating("Sword vs. karate", "Alice", 0);
ratingTable.addRating("Love at last", "Bob", 5);
ratingTable.addRating("Cute puppies of love", "Bob", 4);
ratingTable.addRating("Nonstop car chases", "Bob", 0);
ratingTable.addRating("Sword vs. karate", "Bob", 0);
ratingTable.addRating("Love at last", "Carol", 0);
ratingTable.addRating("Cute puppies of love", "Carol", 0);
ratingTable.addRating("Nonstop car chases", "Carol", 5);
ratingTable.addRating("Sword vs. karate", "Carol", 5);
ratingTable.addRating("Love at last", "Dave", 0);
ratingTable.addRating("Remance forever", "Dave", 0);
ratingTable.addRating("Nonstop car chases", "Dave", 4);

JavaRDD<UserItemRating> input = context.parallelize(ratingTable.getRatings());

CFRecommender recommender = new CFRecommender();
recommender.setMaxIterations(50);
recommender.setFeatureCount(2);

JavaRDD<UserItemRating> output = recommender.fitAndTransform(input);

List<UserItemRating> predicted = output.collect();
for(UserItemRating cell : predicted){
 System.out.println("predict(" + cell.getItem() + ", " + cell.getUser() + "): " + cell.getValue());
}

To find the correlation between any two movies using user rating:

The sample code below tries to find the correlation between items rated by users. Can be used for scenario such as "Customer who bought this also bought"

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");

RatingTable ratingTable =new RatingTable();
ratingTable.addRating("Love at last", "Alice", 5);
ratingTable.addRating("Remance forever", "Alice", 5);
ratingTable.addRating("Nonstop car chases", "Alice", 0);
ratingTable.addRating("Sword vs. karate", "Alice", 0);
ratingTable.addRating("Love at last", "Bob", 5);
ratingTable.addRating("Cute puppies of love", "Bob", 4);
ratingTable.addRating("Nonstop car chases", "Bob", 0);
ratingTable.addRating("Sword vs. karate", "Bob", 0);
ratingTable.addRating("Love at last", "Carol", 0);
ratingTable.addRating("Cute puppies of love", "Carol", 0);
ratingTable.addRating("Nonstop car chases", "Carol", 5);
ratingTable.addRating("Sword vs. karate", "Carol", 5);
ratingTable.addRating("Love at last", "Dave", 0);
ratingTable.addRating("Remance forever", "Dave", 0);
ratingTable.addRating("Nonstop car chases", "Dave", 4);

JavaRDD<UserItemRating> input = context.parallelize(ratingTable.getRatings());

ItemCorrelationRecommender recommender = new ItemCorrelationRecommender();

JavaRDD<ItemCorrelation> output = recommender.fitAndTransform(input);

List<ItemCorrelation> predicted = output.collect();
for(ItemCorrelation cell : predicted){
 System.out.println("movie-correlation(" + cell.getItem1() + ", " + cell.getItem2() + "): " + cell.getPearson());
}

Recommend connection via mutual connections

The sample code below shows how to recommend connections between two individual who do not know each other but might have mutual connections:

List<Connection> connections = new ArrayList<>();
connections.add(new Connection("Alice", Arrays.asList("Bob", "Dave"))); // Alice knows Bob and Dave
connections.add(new Connection("Dave", Arrays.asList("Alice", "Carole")));
connections.add(new Connection("Bob", Arrays.asList("James", "Alice", "Jim")));
connections.add(new Connection("Jim", Arrays.asList("Bob", "Smith")));

JavaSparkContext context = SparkContextFactory.createSparkContext("testing-1");
JavaRDD<Connection> connectionJavaRDD = context.parallelize(connections);
ConnectionRecommender recommender = new ConnectionRecommender();
JavaRDD<ConnectionRecommendation> recommendationJavaRDD = recommender.fitAndTransform(connectionJavaRDD);

List<ConnectionRecommendation> recommendations = recommendationJavaRDD.collect();

for(ConnectionRecommendation recommendation : recommendations){
 System.out.println(recommendation.getPerson1() + " can be connected to " + recommendation.getPerson2() + " via " + recommendation.getCommonFriends());
}

Discrete-event simulator in javascript

js-simulator

https://github.com/chen0040/js-simulator

Inspired by the MASON Multiagent Simulation library in Java, js-simulator is a general-purpose discrete-event multiagent simulator for agent-based modelling and simulation. It was written entirely in Javascript.

Install

Run the following npm command to install

npm install js-simulator

Demo

The following HTML demo is available:

Flocking Boids HTML DEMO
Conway's Game of Life HTML DEMO
School Yard HTML DEMO
L-System (Fractal Plant) HTML DEMO
L-System (Dragon Curve) HTML DEMO
Ant System HTML DEMO
Particle Swarm HTML DEMO
Virus HTML DEMO
(Spring) Balls HTML DEMO
Solar System HTML DEMO
Near Beer Game HTML DEMO

More demo and HTML GUI supports will be added in the subsequent releases.

Usage

Create and schedule discrete events or agents

The discrete-event simulator is managed via the Scheduler class, which can be created as shown below:

jssim = require('js-simulator');
var scheduler = new jssim.Scheduler();

The scheduler schedules and fires events based on their time and rank (i.e. the order of the event) spec.

To schedule the an event to fire at a particular time:

var rank = 1; // the higher the rank, the higher the priority assigned and the higher-rank event will be fired first for all events occurring at the same time interval
var evt = new jssim.SimEvent(rank);
evt.id = 20; 
evt.update = function(deltaTime) {
    console.log('event [' + this.id + '] with rank ' + this.rank + ' is fired at time ' + this.time);
    
    // the code below allows the evt to send message to another agent (i.e., the agent referred by receiver variable)
    /*
    var receiver_id = receiver.guid()
    this.sendMsg(receiver_id, {
        content: "Hello"
    });
    */
    
    // the code below allows the evt to process messages sent from another agent
    /*
    var messages = this.readInbox();
    for(var i = 0; i < messages.length; ++i){
        var msg = messages[i];
        var sender_id = msg.sender;
        var recipient_id = msg.recipient; // should equal to this.guid()
        var time = msg.time;
        var rank = msg.rank; // the messages[0] contains the highest ranked message and last messages contains lowest ranked
        var content = msg.content; // for example the "Hello" text from the sendMsg code above
    }
    */
};

var time_to_fire = 10; // fire this event at time = 10
scheduler.schedule(evt, time_to_fire);

The main logic for an event is defined in its update(deltaTime) method, as shown in the code above. Events with higher ranks and earlier time_to_fire will always be executed first by the scheduler.

An event can also be sheduled to fire at a later time from the current time (e.g., such an event can be fired within another event):

var delta_time_later = 10; // the event will be fired 10 time units from now, where now refers to the current scheduler time
scheduler.scheduleOnceIn(evt, delta_time_later);

In terms of multi-agent system, an event can be thought of as an agent. Such an agent may need to execute repeatedly. In the js-simulator, this is achieved by firing an event repeatedly at a fixed interval:

var interval = 2; // time interval between consecutive firing of the event
var start_time = 12; // time to fire the event for the first time
scheduler.scheduleRepeatingAt(evt, start_time, interval);

If the start_time is at from the start of the simulation, then the above scheduling can also be replaced by:

scheduler.scheduleRepatingIn(evt, interval);

Execute the scheduler loop for the main discrete-event simulation

After the events/agents are scheduled, they are not fired immediately but only fired when scheduler.update() method is called, each call to scheduler.update() to move the time forward. At each time forwarded, events with higher rank will be executed (by calling their update(delaTime) method) first. Also events with the same rank will be shuffled before execution.

The scheduler can be executed in the following loop:

while(scheduler.hasEvents()) {
    var evts_fired = scheduler.update();
}

The above will run until no more events to fire in the scheduler, to stop the scheduler at a particular instead, use the following loop:

while(scheduler.current_time < 20) { // stop the scheduler when current scheduler time is 20
    scheduler.update();
}

The current scheduler time can be obtained by calling (this is useful if we want to know the current time inside the scheduler):

var current_scheduler_time = scheduler.current_time;

Sample Codes

Flocking behavior Demo

The source code below shows how to create a flocking of 15 boids (12 preys and 3 predators) that demonstrate the flocking principles:

Firstly we will declare a Boid class the inherits from the jsssim.SimEvent class, which defines the behavior of a single boid:

var jssim = require('js-simulator');


var Boid = function(id, initial_x, initial_y, space, isPredator) {
    var rank = 1;
    jssim.SimEvent.call(this, rank);
    this.id = id;
    this.space = space;
    this.space.updateAgent(this, initial_x, initial_y);
    this.sight = 75;
    this.speed = 12;
    this.separation_space = 30;
    this.velocity = new jssim.Vector2D(Math.random(), Math.random());
    this.isPredator = isPredator;
    this.border = 100;
};

Boid.prototype = Object.create(jssim.SimEvent);
Boid.prototype.update = function(deltaTime) {
    var boids = this.space.findAllAgents();
    var pos = this.space.getLocation(this.id);

    if(this.isPredator) {
        var prey = null;
        var min_distance = 10000000;
        for (var boidId in boids)
        {
            var boid = boids[boidId];
            if(!boid.isPredator) {
                var boid_pos = this.space.getLocation(boid.id);
                var distance = pos.distance(boid_pos);
                if(min_distance > distance){
                    min_distance = distance;
                    prey = boid;
                }
            }
        }

        if(prey != null) {
            var prey_position = this.space.getLocation(prey.id);
            this.velocity.x += prey_position.x - pos.x;
            this.velocity.y += prey_position.y - pos.y;
        }
    } else {
        for (var boidId in boids)
        {
            var boid = boids[boidId];
            var boid_pos = this.space.getLocation(boid.id);
            var distance = pos.distance(boid_pos);
            if (boid != this && !boid.isPredator)
            {
                if (distance < this.separation_space)
                {
                    // Separation
                    this.velocity.x += pos.x - boid_pos.x;
                    this.velocity.y += pos.y - boid_pos.y;
                }
                else if (distance < this.sight)
                {
                    // Cohesion
                    this.velocity.x += (boid_pos.x - pos.x) * 0.05;
                    this.velocity.y += (boid_pos.y - pos.y) * 0.05;
                }
                if (distance < this.sight)
                {
                    // Alignment
                    this.velocity.x += boid.velocity.x * 0.5;
                    this.velocity.y += boid.velocity.y * 0.5;
                }
            }
            if (boid.isPredator && distance < this.sight)
            {
                // Avoid predators.
                this.velocity.x += pos.x - boid_pos.x;
                this.velocity.y += pos.y - boid_pos.y;
            }
        }
    }


    // check speed
    var speed = this.velocity.length();
    if(speed > this.speed) {
        this.velocity.resize(this.speed);
    }

    pos.x += this.velocity.x;
    pos.y += this.velocity.y;

    // check boundary
    var val = this.boundary - this.border;
    if (pos.x < this.border) pos.x = this.boundary - this.border;
    if (pos.y < this.border) pos.y = this.boundary - this.border;
    if (pos.x > val) pos.x = this.border;
    if (pos.y > val) pos.y = this.border;
        
    console.log("boid [ " + this.id + "] is at (" + pos.x + ", " + pos.y + ") at time " + this.time);
};

Once the boid is defined we can then create and schedule the flocking event simulator using the code below:

var scheduler = new jssim.Scheduler();
scheduler.reset();

var space = new jssim.Space2D();
for(var i = 0; i < 15; ++i) {
    var is_predator = i > 12;
    var boid = new Boid(i, 0, 0, space, is_predator);
    scheduler.scheduleRepeatingIn(boid, 1);
}

while(scheduler.current_time < 20) {
  scheduler.update();
}

Conway's Game of Life

The sample code below shows how to create the game of life simulation:

var jssim = require('js-simulator');

var CellularAgent = function(world) {
  jssim.SimEvent.call(this);
  this.world = world;
}; 

CellularAgent.prototype = Object.create(jssim.SimEvent.prototype);
CellularAgent.prototype.update = function (deltaTime) {
  var width = this.world.width;
  var height = this.world.height;
  var past_grid = this.world.makeCopy();
  for(var i=0; i < width; ++i) {
      for(var j = 0; j < height; ++j) {
          var count = 0;
          for(var dx = -1; dx < 2; ++dx) {
              var x = i + dx;
              if (x >= width) {
                  x = 0;
              }
              if (x < 0) {
                  x = width - 1;
              }
              for(var dy = -1; dy < 2; ++dy) {
                var y = j + dy;
                  if(y >= height) {
                      y = 0;
                  }
                  if(y < 0) {
                      y = height - 1;
                  }
                  count += past_grid.getCell(x, y);
              }
          }
          if (count <= 2 || count >= 5) {
              this.world.setCell(i, j, 0); // dead
          }
          if (count == 3) {
              this.world.setCell(i, j, 1); // live
          }
      }
  }
};

var scheduler = new jssim.Scheduler();
var grid = new jssim.Grid(640, 640);

scheduler.reset();
grid.reset();

grid.setCell(1, 0, 1);
grid.setCell(2, 0, 1);
grid.setCell(0, 1, 1);
grid.setCell(1, 1, 1);
grid.setCell(1, 2, 1);
grid.setCell(2, 2, 1);
grid.setCell(2, 3, 1);

scheduler.scheduleRepeatingIn(new CellularAgent(grid), 1);

while(scheduler.current_time < 20) { // this assumes that we want to terminate at time 20
  scheduler.update();
}

School Yard Demo

The sample code below shows the school yard demo:

var Student = function(id, yard, network) {
   jssim.SimEvent.call(this);
   this.id = id;
   this.yard = yard;
   this.network = network;
   this.MAX_FORCES = 3.0;
   this.forceToSchoolMultiplier = 0.01;
   this.randomMultiplier = 0.1;
};
Student.prototype = Object.create(jssim.SimEvent.prototype);
Student.prototype.update = function(deltaTime) {
   var students = this.yard.findAllAgents();


   var me = this.yard.getLocation(this.id);

    var sumForces = new jssim.Vector2D(0, 0);
    var forceVector = new jssim.Vector2D(0, 0);
    var edges = this.network.adj(this.id);
    var len = edges.length;
    for (var buddy = 0; buddy < len; ++buddy)
    {
        var e = edges[buddy];
        var buddiness = e.info;


        var him = this.yard.getLocation(e.other(this.id));

        if (buddiness >= 0)
        {
            forceVector.set((him.x - me.x) * buddiness, (him.y - me.y) * buddiness);
            if (forceVector.length() > this.MAX_FORCES)
            {
                forceVector.resize(this.MAX_FORCES);
            }
        }
        else
        {
            forceVector.set((me.x - him.x) * buddiness, (me.y - him.y) * buddiness);
            if (forceVector.length() > this.MAX_FORCES)
            {
                forceVector.resize(0);
            }
            else if(forceVector.length() > 0)
            {
                forceVector.resize(this.MAX_FORCES - forceVector.length());
            }
        }

        sumForces.addIn(forceVector);
    }

    sumForces.addIn(
        new jssim.Vector2D((this.yard.width * 0.5 - me.x) * this.forceToSchoolMultiplier, (this.yard.height * 0.5 - me.y) * this.forceToSchoolMultiplier)
        );

    sumForces.addIn(
        new jssim.Vector2D(this.randomMultiplier * (Math.random() * 1.0 - 0.5), this.randomMultiplier * Math.random() * 1.0 - 0.5));

    sumForces.addIn(me);

    me.x = sumForces.x;
    me.y = sumForces.y;

    console.log("Student " + this.id + " is at (" + me.x + ", " + me.y + ") at time " + this.time);
};

var scheduler = new jssim.Scheduler();
var yard = new jssim.Space2D();
var network = new jssim.Network(30);
yard.width = 50;
yard.height = 50;

scheduler.reset();
yard.reset();
network.reset();
for(var i=0; i < 30; ++i) {
   var student = new Student(i, yard, network);
   yard.updateAgent(student, Math.random() * yard.width, Math.random() * yard.height);
   scheduler.scheduleRepeatingIn(student, 1);
}

var buddies = {};
for (var i = 0; i < 30; ++i)
{
    var student = i;
    var studentB = i;
    do
    {
        studentB = Math.floor(Math.random() * 30);
    } while (student == studentB);
    var buddiness = Math.random();
    if(!network.connected(student, studentB)){
        network.addEdge(new jssim.Edge(student, studentB, buddiness));
    }

    var studentB = i;
    do
    {
        studentB = Math.floor(Math.random() * 30);
    } while (student == studentB);

    buddiness = Math.random();
    if(!network.connected(student, studentB)){
        network.addEdge(new jssim.Edge(student, studentB, buddiness));
    }
}

while (scheduler.current_time < 2) {
   scheduler.update();
}

Programming Breaks

Wednesday, June 28, 2017

C++ implementation for Linear Genetic Programming

cpp-linear-genetic-programming

Introduction

Usage

C# codes for working with powerpoint

cs-vsto-powerpoint-writer

Objective

Langauage

Install

Usage

Text compression in Python

pycompressor

Install

Usage:

Recommender engine in Spark

spark-ml-recommender

Feature

Install

Usage

Predict missing ratings

To find the correlation between any two movies using user rating:

Recommend connection via mutual connections

Discrete-event simulator in javascript

js-simulator

Install

Demo

Usage

Create and schedule discrete events or agents

Execute the scheduler loop for the main discrete-event simulation

Sample Codes

Flocking behavior Demo

Conway's Game of Life

School Yard Demo

Blog Archive

Labels