hopf.c

hopfield 算法的实现与应用。附带demo演示

/*----------------------------------------------------------------------
  File    : hopfield.c
  Contents: Hopfield network as associative memory
  Author  : Christian Borgelt
  History : 2002.12.01 file created from file som.c
----------------------------------------------------------------------*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "hopf.h"

/*----------------------------------------------------------------------
  Functions
----------------------------------------------------------------------*/

HOPFNET* hfn_create (int width, int height)
{                               /* --- create a Hopfield network */
  int     i, n;                 /* loop variable, number of neurons */
  HOPFNET *hfn;                 /* created Hopfield network */
  int     *v;                   /* vector of activations/weights */

  assert((width > 1) && (height > 0));
  n   = width *height;          /* compute the number of neurons */
  hfn = (HOPFNET*)malloc(sizeof(HOPFNET) +(height+n+n-1) *sizeof(int*));
  if (!hfn) return NULL;        /* allocate the network body */
  v   = (int*)malloc((n +2*n*n) *sizeof(int));
  if (!v) { free(hfn); return NULL; }
  hfn->width   = width;         /* allocate the vectors/matrices */
  hfn->height  = height;        /* and initialize the fields */
  hfn->unitcnt = n;
  hfn->wgts    = hfn->acts +height;
  hfn->pats    = hfn->wgts +n;
  for (i = 0; i < height; i++) { hfn->acts[i] = v; v += width; }
  for (i = 0; i < n;      i++) { hfn->wgts[i] = v; v += n; }
  for (i = 0; i < n;      i++) { hfn->pats[i] = v; v += n; }
  hfn_init(hfn);                /* initialize weights and activations */
  return hfn;                   /* return the created network */
}  /* hfn_create() */

/*--------------------------------------------------------------------*/

void hfn_delete (HOPFNET *hfn)
{                               /* --- delete a Hopfield network */
  assert(hfn);                  /* check the function argument */
  free(hfn->acts[0]);           /* delete the vectors/matrices */
  free(hfn);                    /* and the network body */
}  /* hfn_delete() */

/*--------------------------------------------------------------------*/

void hfn_init (HOPFNET *hfn)
{                               /* --- init. a Hopfield network */
  int i, *v;                    /* loop variable, unit/weight vector */

  assert(hfn);                  /* check the function argument */
  for (v = hfn->acts[0] +(i = hfn->unitcnt);               --i >= 0; )
    *--v = 0;                   /* clear all activations */
  for (v = hfn->acts[0] +(i = hfn->unitcnt);               --i >= 0; )
    *--v = 0;                   /* clear all activations */
  for (v = hfn->wgts[0] +(i = hfn->unitcnt *hfn->unitcnt); --i >= 0; )
    *--v = 0;                   /* clear all weights */
  for (v = hfn->pats[hfn->unitcnt-1]  +(i = hfn->unitcnt); --i >= 0; )
    *--v = i;                   /* initialize the neuron order */
  hfn->patcnt = 0;              /* delete all patterns */
  hfn->curr   = 0;              /* initialize update index */
}  /* hfn_init() */

/*--------------------------------------------------------------------*/

void hfn_shuffle (HOPFNET *hfn, double randfn(void))
{                               /* --- shuffle neurons */
  int n, i;                     /* loop variables */
  int *v;                       /* to traverse the vector */
  int t;                        /* exchange buffer */

  assert(hfn && randfn);        /* check the function arguments */
  n = hfn->unitcnt; v = hfn->pats[n-1];
  while (--n > 0) {             /* shuffle loop (n random selections) */
    i = (int)((n+1) *randfn()); /* compute a random index */
    if (i > n) i = n;           /* in the remaining section and */
    if (i < 0) i = 0;           /* exchange the vector elements */
    t = v[i]; v[i] = v[n]; v[n] = t;
  }
}  /* hfn_shuffle() */

/*--------------------------------------------------------------------*/

void hfn_clear (HOPFNET *hfn)
{                               /* --- clear all activations */
  int i, *v;                    /* loop variable, unit/weight vector */

  assert(hfn);                  /* check the function argument */
  for (v = hfn->acts[0] +(i = hfn->unitcnt); --i >= 0; )
    *--v = -1;                  /* clear all activations */
}  /* hfn_clear() */

/*--------------------------------------------------------------------*/

void hfn_rand (HOPFNET *hfn, double randfn(void))
{                               /* --- randomize a Hopfield network */
  int i, *v;                    /* loop variable, unit/weight vector */

  assert(hfn);                  /* check the function argument */
  for (v = hfn->acts[0] +(i = hfn->unitcnt); --i >= 0; )
    *--v = (randfn() >= 0.5) ? 1 : -1;
}  /* hfn_rand() */             /* set random activations */

/*--------------------------------------------------------------------*/

void hfn_curr (HOPFNET *hfn, int *x, int *y)
{                               /* --- get the current neuron */
  int i;                        /* neuron index */

  assert(hfn && x && y);        /* check the function arguments */
  i  = hfn->pats[hfn->unitcnt-1][hfn->curr];
  *x = i % hfn->width;          /* get the coordinates */
  *y = i / hfn->width;          /* of the next neuron to update */
}  /* hfn_curr() */

/*--------------------------------------------------------------------*/

static int _update (HOPFNET *hfn, int i)
{                               /* --- update an activation */
  int k;                        /* loop variable */
  int *wgt, *act;               /* weight and activation vector */
  int sum = 0;                  /* weighted sum of inputs */

  assert(hfn                    /* check the function arguments */
     && (i >= 0) && (i < hfn->unitcnt));
  wgt = hfn->wgts[i] +(k = hfn->unitcnt);
  act = hfn->acts[0] + k;       /* compute the network input */
  while (--k >= 0) sum += *--act * *--wgt;
  return hfn->acts[0][i] = (sum >= 0) ? 1 : -1;
}  /* _update() */              /* set and return new activation */

/*--------------------------------------------------------------------*/

int hfn_update (HOPFNET *hfn, int x, int y)
{                               /* --- update activation(s) */
  int *v;                       /* random order of the neurons */

  assert(hfn);                  /* check the function argument */
  if ((x >= 0) && (y >= 0))     /* if to update one specific neuron */
    return _update(hfn, x *hfn->height +y);
  v = hfn->pats[hfn->unitcnt -1];
  if (y >= 0) {                 /* if to update the next neuron */
    x = _update(hfn, v[hfn->curr]);
    if (++hfn->curr >= hfn->unitcnt) hfn->curr = 0;
    return x;                   /* update the neuron and */
  }                             /* advance the neuron index */
  for (x = hfn->unitcnt; --x >= 0; )
    _update(hfn, v[x]);         /* traverse and update all neurons */
  return 0;                     /* return 'ok' */
}  /* hfn_update() */

/*--------------------------------------------------------------------*/

int hfn_patadd (HOPFNET *hfn)
{                               /* --- add a pattern to the network */
  int x, y;                     /* loop variables */
  int *w, *a;                   /* to traverse the weights/activ.s */

  assert(hfn);                  /* check the function argument */
  if (hfn->patcnt >= hfn->unitcnt -1)
    return -1;                  /* check the network capacity */
  a = hfn->acts[0] +(x = hfn->unitcnt);
  w = hfn->pats[hfn->patcnt++] +x;  /* store the current activation */
  while (--x >= 0) { --a; *--w = *a = (*a > 0) ? 1 : -1; }
  for (x = hfn->unitcnt; --x >= 0; ) {
    for (w = hfn->wgts[x] +(y = hfn->unitcnt); --y >= 0; )
      *--w += a[x]*a[y];        /* compute the outer product, */
    w[x] = 0;                   /* add it to the weight matrix, */
  }                             /* and set the diagonal to 0 */
  return 0;                     /* return 'ok' */
}  /* hfn_patadd() */

/*--------------------------------------------------------------------*/

void hfn_patrem (HOPFNET *hfn, int index)
{                               /* --- remove a pattern */
  int x, y;                     /* loop variables */
  int *w, *a;                   /* to traverse the weights/activ.s */

  assert(hfn);                  /* check the function argument */
  a = hfn->pats[index];         /* remove the pattern */
  hfn->pats[index] = hfn->pats[hfn->patcnt-1];
  hfn->pats[--hfn->patcnt] = a;
  for (x = hfn->unitcnt; --x >= 0; ) {
    for (w = hfn->wgts[x] +(y = hfn->unitcnt); --y >= 0; )
      *--w -= a[x]*a[y];        /* compute the outer product, */
    w[x] = 0;                   /* subtract it from the weights, */
  }                             /* and set the diagonal to 0 */
}  /* hfn_patrem() */

/*--------------------------------------------------------------------*/

void hfn_patget (HOPFNET *hfn, int index)
{                               /* --- get a stored pattern */
  int i;                        /* loop variable */
  int *p, *a;                   /* to traverse the pattern/activ.s */

  assert(hfn                    /* check the function arguments */
     && (index >= 0) && (index < hfn->patcnt));
  p = hfn->pats[index] +(i = hfn->unitcnt);
  a = hfn->acts[0]     + i;     /* copy the pattern */
  while (--i >= 0) *--a = *--p; /* into the neuron activations */
}  /* hfn_patget() */

/*--------------------------------------------------------------------*/

int hfn_patfind (HOPFNET *hfn)
{                               /* --- find a pattern */
  int i, k;                     /* loop variables */
  int *p, *a;                   /* to traverse the pattern/activ.s */

  assert(hfn);                  /* check the function argument */
  for (k = hfn->patcnt; --k >= 0; ) {
    p = hfn->pats[k] +(i = hfn->unitcnt);
    for (a = hfn->acts[0] +i; --i >= 0; )
      if (*--a != *--p) break;  /* traverse the patterns and */
    if (i < 0) return k;        /* compare them to the activations */
  }                             /* if equal, return pattern index */
  return -1;                    /* return 'pattern not found' */
}  /* hfn_patfind() */

/*--------------------------------------------------------------------*/

int hfn_save (HOPFNET *hfn, FILE *file)
{                               /* --- save network to a file */
  int i, x, y;                  /* loop variables */
  int *v;                       /* to traverse the patterns */

  assert(hfn && file);          /* check the function arguments */
  fprintf(file, "%d %d\n", hfn->width, hfn->height);
  for (i = 0; i < hfn->patcnt; i++) {
    v = hfn->pats[i];           /* traverse the patterns */
    fputc('\n', file);          /* add an empty line between patterns */
    for (y = 0; y < hfn->height; y++) {
      for (x = 0; x < hfn->width; x++)
        fputc((*v++ > 0) ? '1' : '0', file);
      fputc('\n', file);        /* print each pattern */
    }                           /* as a matrix of 0s and 1s */
  }
  return (ferror(file)) ? -1 : 0;
}  /* hfn_save() */

/*--------------------------------------------------------------------*/

HOPFNET* hfn_load (FILE *file)
{                               /* --- load network from a file */
  int     x, y;                 /* loop variables */
  int     c;                    /* character read */
  int     *a;                   /* to traverse the activation vector */
  HOPFNET *hfn;                 /* created self-organizing map */

  assert(file);                 /* check the function argument */
  if (fscanf(file, "%d%d", &x, &y) != 2)
    return NULL;                /* read width and height */
  hfn = hfn_create(x, y);       /* create a Hopfield network */
  if (!hfn) return NULL;        /* with the read dimensions */
  do { c = fgetc(file);         /* find the end of the line */
  } while ((c != '\n') && (c != EOF));
  while (fgetc(file) == '\n') { /* while there is another pattern */
    a = hfn->acts[0];           /* get the activation vector */
    for (y = 0; y < hfn->height; y++) {
      for (x = 0; x < hfn->width; x++) {
        c = fgetc(file);        /* read character by character */
        if ((c != '1') && (c != '0')) {
          hfn_delete(hfn); return NULL; }
        *a++ = (c == '1') ? 1 : -1;
      }                         /* set the activations */
      do { c = fgetc(file);     /* find the end of the line */
      } while ((c != '\n') && (c != EOF));
      if (c != '\n') { hfn_delete(hfn); return NULL; }
    }
    if (hfn_patadd(hfn) != 0) { /* store the pattern read */
      hfn_delete(hfn); return NULL; }
  }                             /* check for a read error */
  if (ferror(file)) { hfn_delete(hfn); return NULL; }
  return hfn;                   /* return the created network */
}  /* hfn_load() */