ggreedysearch.cpp

一个非常有用的开源代码

/*
	Copyright (C) 2006, Mike Gashler

	This library is free software; you can redistribute it and/or
	modify it under the terms of the GNU Lesser General Public
	License as published by the Free Software Foundation; either
	version 2.1 of the License, or (at your option) any later version.

	see http://www.gnu.org/copyleft/lesser.html
*/

#include "GGreedySearch.h"
#include "GBits.h"
#include <math.h>
#include <stdio.h>


GMomentumGreedySearch::GMomentumGreedySearch(GRealVectorCritic* pCritic)
: GRealVectorSearch(pCritic)
{
	m_nDimensions = pCritic->GetVectorSize();
	m_nCurrentDim = 0;
	m_pVector = new double[m_nDimensions];
	m_pStepSizes = new double[m_nDimensions];
	m_dChangeFactor = .93;
	int i;
	for(i = 0; i < m_nDimensions; i++)
	{
		m_pVector[i] = 0;
		m_pStepSizes[i] = 1;
	}
	m_dError = pCritic->Critique(m_pVector);
}

/*virtual*/ GMomentumGreedySearch::~GMomentumGreedySearch()
{
	delete(m_pVector);
	delete(m_pStepSizes);
}

/*virtual*/ void GMomentumGreedySearch::Iterate()
{
	m_pVector[m_nCurrentDim] += m_pStepSizes[m_nCurrentDim];
	double dError = m_pCritic->Critique(m_pVector);
	if(dError >= m_dError)
	{
		m_pVector[m_nCurrentDim] -= m_pStepSizes[m_nCurrentDim];
		m_pVector[m_nCurrentDim] -= m_pStepSizes[m_nCurrentDim];
		dError = m_pCritic->Critique(m_pVector);
		if(dError >= m_dError)
			m_pVector[m_nCurrentDim] += m_pStepSizes[m_nCurrentDim];
	}
	if(dError >= m_dError)
		m_pStepSizes[m_nCurrentDim] *= m_dChangeFactor;
	else
	{
		m_pStepSizes[m_nCurrentDim] /= m_dChangeFactor;
		m_dError = dError;
	}
	if(++m_nCurrentDim >= m_nDimensions)
		m_nCurrentDim = 0;
}	



// --------------------------------------------------------------------------------


GStochasticGreedySearch::GStochasticGreedySearch(GRealVectorCritic* pCritic, double dMin, double dRange)
: GRealVectorSearch(pCritic)
{
	m_dRange = dRange;
	m_dConservativeness = 4;
	m_nDimensions = pCritic->GetVectorSize();
	m_pVector = new double[m_nDimensions];
	m_pTest = new double[m_nDimensions];
	int i;
	for(i = 0; i < m_nDimensions; i++)
		m_pVector[i] = GBits::GetRandomDouble() * dRange + dMin;
	m_dError = pCritic->Critique(m_pVector);
}

/*virtual*/ GStochasticGreedySearch::~GStochasticGreedySearch()
{
	delete(m_pVector);
	delete(m_pTest);
}

/*virtual*/ void GStochasticGreedySearch::Iterate()
{
	// Pick a new spot to try
	int i;
	for(i = 0; i < m_nDimensions; i++)
	{
		if(rand() & 1)
			m_pTest[i] = m_pVector[i] + (m_dRange * pow(GBits::GetRandomDouble(), m_dConservativeness));
		else
			m_pTest[i] = m_pVector[i] - (m_dRange * pow(GBits::GetRandomDouble(), m_dConservativeness));
	}

	// Critique the current spots and find the global best
	double dError = m_pCritic->Critique(m_pTest);
	if(dError < m_dError)
	{
		double* pTmp = m_pTest;
		m_pTest = m_pVector;
		m_pVector = pTmp;
		m_dError = dError;
	}
}


// --------------------------------------------------------------------------------

GActionGreedySearch::GActionGreedySearch(GActionPathCritic* pCritic)
: GActionPathSearch(pCritic)
{
	m_pTmpState = new double[m_pCritic->GetVectorSize()];
}

// virtual
GActionGreedySearch::~GActionGreedySearch()
{
	delete(m_pTmpState);
}

// virtual
bool GActionGreedySearch::Iterate()
{
	GActionPath* pPath = m_pCritic->GetPath(0);
	double dDeltaError;
	double dBestDeltaError = 0;
	int nBestAction = 0;
	int i;
	for(i = 0; i < m_pCritic->GetActionCount(); i++)
	{
		m_pCritic->DoAction(pPath, i, m_pTmpState);
		dDeltaError = m_pCritic->CritiqueAction(pPath, i, m_pTmpState) - pPath->GetError();
		if(dDeltaError < dBestDeltaError)
		{
			dBestDeltaError = dDeltaError;
			nBestAction = i;
		}
	}
	if(dBestDeltaError < 0)
	{
		m_pCritic->DoAction(pPath, nBestAction, m_pTmpState);
		m_pTmpState = pPath->AddAction(dBestDeltaError + pPath->GetError(), nBestAction, m_pTmpState);
		return false;
	}
	return true;	
}