Wednesday, August 25, 2010

Fuzzy Logic Experiments in F#

In an earlier post, I mentioned I was reading Fuzzy Logic With Engineering Applications by Timothy J. Ross. It’s an excellent book, and I’ve been doing some experiments in F# based on my readings in the book. This post outlines some classes and functions I’ve created, and the next post will show a simple test application. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

My basic approach was to code each fuzzy set as a series of right trapezoids. This is not the only approach, and other methods – such as continuous functions or symmetric triangles – may be more appropriate for some situations. I call my trapezoid implementation a “tzoid,” and it’s basic features are shown in the diagram below (refer also to the code at the bottom of this post).

A fuzzy set is composed of an ordered collection of tzoids. The collection can be an array, list, sequence, etc., as appropriate; all are considered equivalent for the purposes of defining a set.

The basic fuzzy inference process is this: for each rule, determine the degree of membership of one or more “crisp” values in an antecedent set or sets (“fuzzification”), and use this to estimate the membership in a consequent set. Combine these consequent set memberships and “defuzzify” them into a “crisp” output value.

There are a large number of methods for doing this, each with various pros and cons; I comment you to Fuzzy Logic With Engineering Applications for a detailed discussion. My method here is as follows:

1) Compute the degree of membership of each crisp input parameter as the height of the fuzzy set at that parameter. (Fuzzification.)

2) Combine these degrees of membership using a “min” function. (Conjunction.)

3) Compute the crisp output value by a) truncating each output set at the corresponding height from steps 1 and 2, b) finding the centroid, and c) computing the weighted average (by set area) of all the centroids. (Defuzzification.)

The diagrams below show the operations of finding the height, finding an individual tzoid fractional area (ntroid), and finding a fractional area for an entire fuzzy set (ntroidz). The code shows how the centroidz is found as the ntroidz of half the set area, and a how a “project” function is used to truncate an output set and project a crisp value from its centroid. (There is also a normalize function, which is reserved for future use.)

That’s it. My next post will show how these functions can be combined to make a simple inference system.

module Trapezoid
open System.Collections.Generic
// Defines a right trapeziodal area.
// (Trapezoid is called trapezium in British English, IIRC.)
type tzoid =
    X0 : float;
    Y0 : float;
    X1 : float;
    Y1 : float;
    Slope : float;
    Intercept : float;
  member this.X y =
    match this.Slope with 
    | 0.0 -> this.X0 
    | _ -> (y-this.Intercept)/this.Slope
  member this.Y x =
  member this.Area =
  static member Make x0 y0 x1 y1 = 
    let slope = (y1-y0)/(x1-x0) 
      X0=x0; Y0=y0; X1=x1; Y1=y1;
// Turns a sequence of pairs into
// a sequence of tzoids. 
let ofSeq s =
  |> Seq.pairwise 
  |> (fun ((x0,y0),(x1,y1))->tzoid.Make x0 y0 x1 y1)
// Returns true if the tops of the tzoids are colinear.
let colinear (t0:tzoid) (t1:tzoid) =
// Truncates a tzoid, possibly splitting it.
// Designed for use with fold functions.
let truncate y tr acc =
  match ((y<tr.Y0)&&(y>tr.Y1))||((y>tr.Y0)&&(y<tr.Y1)) with
  | true -> 
    let xn = tr.X y
    (tzoid.Make tr.X0 (min tr.Y0 y) xn y)::
    (tzoid.Make xn y tr.X1 (min tr.Y1 y))::
  | false -> 
    (tzoid.Make tr.X0 (min y tr.Y0) 
                tr.X1 (min y tr.Y1))::acc
// Normalize a tzoid by combining colinear neighbors.
// Designed for use with fold functions.
let normalize tr acc =
  match acc with 
  | h::t ->
    match colinear h tr with
    | false -> tr::acc
    | true -> (tzoid.Make tr.X0 tr.Y0 h.X1 h.Y1)::t
  | [] -> [tr]
// X value for a given area (a) in a tzoid.
let ntroid x0 x1 y m a = 
  match m with
  | 0.0 -> 
    match y with
    | 0.0 -> (x0+x1)/2.0
    | _ -> a/y+x0 
  | _ -> x0+(sqrt(y*y+2.0*a*m)-y)/m
// X value for a given area (a) in
// a list of tzoids.
let ntroidz a (l:tzoid list) =
  let rec f acc (l:tzoid list) =
    match l with 
    | h::t -> 
      let acc0 = h.Area+acc
      match acc0>=a with
      | true -> ntroid h.X0 h.X1 h.Y0 h.Slope (a-acc)
      | _ -> f acc0 t 
    | _ -> System.Double.NaN
  match a with
  | 0.0 ->
    match l with 
    | [] -> System.Double.NaN 
    | h::t -> 
      (h.X0+(List.nth l ((List.length l)-1)).X1)/2.0
  | _ -> f 0.0 l
// Centroid X value for a list of tzoids.
let centroidz (l:tzoid list) =
  let a = List.sumBy (fun (t:tzoid)->t.Area) l
  a,(ntroidz (a/2.0) l)
// Garden-variety binary search.
let inline bsearch (cmp:'V0->int) (a:'V0[]) =
  let rec f lo hi =
    match lo>hi with
    | true -> None
    | _ ->
      let mid = lo+(hi-lo)/2
      match cmp a.[mid] with
      | 0 -> Some(a.[mid])
      | x when x<0 -> f (mid+1) hi
      | _ -> f lo (mid-1)
  f 0 (a.Length-1)
// Find height at x in a list of tzoids.
let height x (a:tzoid[]) =
  let f (t:tzoid) = 
    match x<t.X0 with
    | true -> 1
    | _ ->
    match x>t.X1 with
    | true -> -1
    | _ -> 0
  match bsearch f a with
  | None -> 0.0
  | Some(t) -> t.Y x
// Truncate a tozid array at height h
// and return the new centroid.
let project (a:tzoid[]) h =
  Array.foldBack (truncate h) a []
  |> centroidz

No comments: