pareto-frontier.tsā¢30.5 kB
/**
* Pareto Frontier Management System for Multi-Objective Optimization
*
* This implementation provides efficient Pareto dominance checking, candidate management,
* and sampling strategies for genetic evolutionary prompt adaptation.
*/
import type { PromptCandidate } from '../types/gepa';
import { MemoryLeakIntegration } from './memory-leak-detector';
import { executeComputationWithResilience } from './resilience/index';
/**
* Objective function definition for Pareto optimization
*/
export interface ParetoObjective {
name: string;
weight: number;
direction: 'maximize' | 'minimize';
extractor: (candidate: PromptCandidate) => number;
}
/**
* Point in the Pareto frontier with objectives and metadata
*/
export interface ParetoPoint {
candidate: PromptCandidate;
objectives: Map<string, number>;
dominationCount: number;
rank: number;
}
/**
* Sampling strategy configuration
*/
export interface SamplingStrategy {
name: 'uniform' | 'ucb' | 'epsilon-greedy' | 'pareto-based';
parameters?: {
epsilon?: number;
confidence?: number;
exploration?: number;
};
}
/**
* Configuration for Pareto frontier management
*/
export interface ParetoFrontierConfig {
objectives: ParetoObjective[];
maxSize?: number;
samplingStrategy?: SamplingStrategy;
archiveEnabled?: boolean;
}
/**
* Convergence metrics for analyzing frontier quality
*/
export interface ConvergenceMetrics {
diversity: number;
spacing: number;
spread: number;
hypervolume: number;
generationalDistance: number;
}
/**
* Statistical summary of frontier state
*/
export interface FrontierStatistics {
totalCandidates: number;
frontierSize: number;
averageRank: number;
objectives: Map<string, { min: number; max: number; mean: number; std: number }>;
convergenceHistory: ConvergenceMetrics[];
}
/**
* Main Pareto Frontier implementation supporting multi-objective optimization
*/
export class ParetoFrontier {
private frontier: ParetoPoint[] = [];
private archive: ParetoPoint[] = [];
private config: ParetoFrontierConfig;
private convergenceHistory: ConvergenceMetrics[] = [];
// OPTIMIZATION: Caching and indexing for performance
private objectiveCache = new Map<string, Map<string, number>>();
private dominanceIndex = new DominanceIndex();
private lastUpdateTimestamp = 0;
private hypervolumeCache = new Map<string, { value: number; timestamp: number }>();
constructor(config: ParetoFrontierConfig) {
this.config = config;
this.setupMemoryLeakDetection();
}
/**
* Add a candidate to the frontier, maintaining Pareto optimality (OPTIMIZED)
*/
async addCandidate(candidate: PromptCandidate): Promise<boolean> {
return await executeComputationWithResilience(
async () => {
return this.addCandidateInternal(candidate);
},
{
context: {
name: 'pareto-add-candidate',
priority: 'medium'
}
}
);
}
/**
* Internal implementation of addCandidate with resilience protection
*/
private async addCandidateInternal(candidate: PromptCandidate): Promise<boolean> {
const point = this.createPoint(candidate);
// OPTIMIZATION: Use dominance index for O(log n) checking instead of O(n)
if (this.dominanceIndex.isDominated(point)) {
return false;
}
// OPTIMIZATION: Quick identity check using cached objectives
const candidateObjectives = this.getCachedObjectives(candidate);
const isIdentical = this.frontier.some(existing =>
this.areObjectivesIdentical(candidateObjectives, existing.objectives)
);
if (isIdentical) {
return false;
}
// OPTIMIZATION: Use spatial indexing to find dominated points efficiently
const dominatedPoints = this.dominanceIndex.findDominated(point);
const nonDominatedPoints = this.frontier.filter(existing =>
!dominatedPoints.some(dominated => dominated.candidate.id === existing.candidate.id)
);
// Add new point to frontier
nonDominatedPoints.push(point);
this.frontier = nonDominatedPoints;
// Track memory allocation for leak detection
const candidateSize = this.estimateCandidateSize(candidate);
MemoryLeakIntegration.trackParetoOperation('add', candidate.id, candidateSize);
// OPTIMIZATION: Update dominance index
this.dominanceIndex.addPoint(point);
if (dominatedPoints.length > 0) {
this.dominanceIndex.removePoints(dominatedPoints);
// Track removed candidates for leak detection
for (const dominatedPoint of dominatedPoints) {
const removedSize = this.estimateCandidateSize(dominatedPoint.candidate);
MemoryLeakIntegration.trackParetoOperation('remove', dominatedPoint.candidate.id, removedSize);
}
}
// Enforce size limit if configured
if (this.config.maxSize && this.frontier.length > this.config.maxSize) {
await this.enforceMaxSize();
}
// Archive removed points if archiving is enabled
if (this.config.archiveEnabled && dominatedPoints.length > 0) {
this.archive.push(...dominatedPoints);
}
// OPTIMIZATION: Track convergence metrics less frequently
if (this.shouldUpdateConvergenceMetrics()) {
this.convergenceHistory.push(this.getConvergenceMetrics());
}
this.lastUpdateTimestamp = Date.now();
return true;
}
/**
* Check if one candidate dominates another
*/
isDominated(candidate: PromptCandidate, by?: PromptCandidate): boolean {
const candidatePoint = this.createPoint(candidate);
if (by) {
const byPoint = this.createPoint(by);
return this.dominates(byPoint, candidatePoint);
}
return this.frontier.some(point => this.dominates(point, candidatePoint));
}
/**
* Get all candidates dominated by the given candidate
*/
getDominatedCandidates(candidate: PromptCandidate): ParetoPoint[] {
const candidatePoint = this.createPoint(candidate);
return this.frontier.filter(point => this.dominates(candidatePoint, point));
}
/**
* Get current Pareto frontier
*/
getFrontier(): ParetoPoint[] {
return [...this.frontier];
}
/**
* Sample a candidate using the specified strategy
*/
async sampleCandidate(strategy?: SamplingStrategy): Promise<PromptCandidate | null> {
return await executeComputationWithResilience(
async () => {
return this.sampleCandidateInternal(strategy);
},
{
context: {
name: 'pareto-sample-candidate',
priority: 'low'
}
}
);
}
/**
* Internal implementation of sampleCandidate with resilience protection
*/
private async sampleCandidateInternal(strategy?: SamplingStrategy): Promise<PromptCandidate | null> {
if (this.frontier.length === 0) return null;
const samplingStrategy = strategy || this.config.samplingStrategy || { name: 'uniform' };
switch (samplingStrategy.name) {
case 'uniform':
return this.sampleUniform();
case 'ucb':
return this.sampleUCB(samplingStrategy.parameters?.confidence || 1.96);
case 'epsilon-greedy':
return this.sampleEpsilonGreedy(samplingStrategy.parameters?.epsilon || 0.1);
default:
return this.sampleUniform();
}
}
/**
* Sample uniformly from frontier
*/
async sampleUniform(): Promise<PromptCandidate | null> {
if (this.frontier.length === 0) return null;
const randomIndex = Math.floor(Math.random() * this.frontier.length);
const selected = this.frontier[randomIndex];
return selected ? selected.candidate : null;
}
/**
* Sample using Upper Confidence Bound strategy
*/
async sampleUCB(confidence: number): Promise<PromptCandidate | null> {
if (this.frontier.length === 0) return null;
const scores = this.frontier.map(point => {
const avgScore = point.candidate.averageScore;
const uncertainty = confidence * Math.sqrt(Math.log(this.frontier.length) / (point.candidate.rolloutCount || 1));
return avgScore + uncertainty;
});
const maxIndex = scores.indexOf(Math.max(...scores));
const selected = this.frontier[maxIndex];
return selected ? selected.candidate : null;
}
/**
* Sample using epsilon-greedy strategy
*/
async sampleEpsilonGreedy(epsilon: number): Promise<PromptCandidate | null> {
if (this.frontier.length === 0) return null;
if (Math.random() < epsilon) {
return this.sampleUniform();
}
// Exploit: select best candidate by average score
const bestPoint = this.frontier.reduce((best, current) =>
current.candidate.averageScore > best.candidate.averageScore ? current : best
);
return bestPoint ? bestPoint.candidate : null;
}
/**
* Compute hypervolume indicator (OPTIMIZED with caching)
*/
computeHypervolume(reference?: Map<string, number>): number {
if (this.frontier.length === 0) return 0;
// OPTIMIZATION: Cache hypervolume calculations
const cacheKey = this.getHypervolumeCacheKey(reference);
const cached = this.hypervolumeCache.get(cacheKey);
if (cached && cached.timestamp > this.lastUpdateTimestamp) {
return cached.value;
}
const ref = reference || this.computeReferencePoint();
// OPTIMIZATION: Use more efficient hypervolume calculation
const hypervolume = this.computeHypervolumeOptimized(ref);
// Cache the result
this.hypervolumeCache.set(cacheKey, {
value: hypervolume,
timestamp: Date.now()
});
return hypervolume;
}
/**
* Get convergence metrics
*/
getConvergenceMetrics(): ConvergenceMetrics {
if (this.frontier.length === 0) {
return {
diversity: 0,
spacing: 0,
spread: 0,
hypervolume: 0,
generationalDistance: 0
};
}
const diversity = this.computeDiversity();
const spacing = this.computeSpacing();
const spread = this.computeSpread();
const hypervolume = this.computeHypervolume();
const generationalDistance = this.computeGenerationalDistance();
return {
diversity,
spacing,
spread,
hypervolume,
generationalDistance
};
}
/**
* Optimize archive to target size while preserving diversity
*/
async optimizeArchive(targetSize: number): Promise<ParetoPoint[]> {
if (this.frontier.length <= targetSize) {
return [...this.frontier];
}
// Simple diversity-preserving selection
// In practice, would use more sophisticated algorithms like SPEA2 or NSGA-II
const selected: ParetoPoint[] = [];
const remaining = [...this.frontier];
// Select most diverse points
while (selected.length < targetSize && remaining.length > 0) {
if (selected.length === 0) {
// Select random first point
const randomIndex = Math.floor(Math.random() * remaining.length);
const firstPoint = remaining.splice(randomIndex, 1)[0];
if (firstPoint) selected.push(firstPoint);
} else {
// Select point with maximum minimum distance to selected points
let maxMinDist = -1;
let bestIndex = 0;
for (let i = 0; i < remaining.length; i++) {
const point = remaining[i];
if (point) {
const minDist = Math.min(...selected.map(sel => this.computeDistance(point, sel)));
if (minDist > maxMinDist) {
maxMinDist = minDist;
bestIndex = i;
}
}
}
const bestPoint = remaining.splice(bestIndex, 1)[0];
if (bestPoint) selected.push(bestPoint);
}
}
return selected;
}
/**
* Get frontier size
*/
size(): number {
return this.frontier.length;
}
/**
* Clear frontier and archive
*/
clear(): void {
// Track bulk deallocation for leak detection
for (const point of this.frontier) {
const candidateSize = this.estimateCandidateSize(point.candidate);
MemoryLeakIntegration.trackParetoOperation('remove', point.candidate.id, candidateSize);
}
for (const point of this.archive) {
const candidateSize = this.estimateCandidateSize(point.candidate);
MemoryLeakIntegration.trackParetoOperation('remove', point.candidate.id, candidateSize);
}
this.frontier = [];
this.archive = [];
this.convergenceHistory = [];
// Clear caches to prevent memory leaks
this.objectiveCache.clear();
this.hypervolumeCache.clear();
}
/**
* Get comprehensive statistics
*/
getStatistics(): FrontierStatistics {
const objectiveStats = new Map<string, { min: number; max: number; mean: number; std: number }>();
this.config.objectives.forEach(obj => {
const values = this.frontier.map(point => point.objectives.get(obj.name) || 0);
if (values.length > 0) {
const mean = values.reduce((a, b) => a + b, 0) / values.length;
const variance = values.reduce((a, b) => a + Math.pow(b - mean, 2), 0) / values.length;
objectiveStats.set(obj.name, {
min: Math.min(...values),
max: Math.max(...values),
mean,
std: Math.sqrt(variance)
});
}
});
return {
totalCandidates: this.frontier.length + this.archive.length,
frontierSize: this.frontier.length,
averageRank: this.frontier.reduce((sum, point) => sum + point.rank, 0) / this.frontier.length || 0,
objectives: objectiveStats,
convergenceHistory: [...this.convergenceHistory]
};
}
// Private helper methods
/**
* Check if point a dominates point b
*/
private dominates(a: ParetoPoint, b: ParetoPoint): boolean {
let betterInAny = false;
let equalInAll = true;
for (const obj of this.config.objectives) {
const aValue = a.objectives.get(obj.name) || 0;
const bValue = b.objectives.get(obj.name) || 0;
// Handle NaN values gracefully
if (isNaN(aValue) || isNaN(bValue)) {
if (isNaN(aValue) && !isNaN(bValue)) return false;
if (!isNaN(aValue) && isNaN(bValue)) betterInAny = true;
equalInAll = false;
continue;
}
if (obj.direction === 'maximize') {
if (aValue < bValue) return false;
if (aValue > bValue) {
betterInAny = true;
equalInAll = false;
} else if (aValue !== bValue) {
equalInAll = false;
}
} else {
if (aValue > bValue) return false;
if (aValue < bValue) {
betterInAny = true;
equalInAll = false;
} else if (aValue !== bValue) {
equalInAll = false;
}
}
}
// If all objectives are equal, no domination
if (equalInAll) return false;
return betterInAny;
}
/**
* Create a Pareto point from a candidate
*/
private createPoint(candidate: PromptCandidate): ParetoPoint {
const objectives = new Map<string, number>();
this.config.objectives.forEach(obj => {
try {
const value = obj.extractor(candidate);
objectives.set(obj.name, isNaN(value) ? 0 : value);
} catch {
// Handle extraction errors gracefully
objectives.set(obj.name, 0);
}
});
return {
candidate,
objectives,
dominationCount: 0,
rank: 1
};
}
/**
* Compute reference point for hypervolume calculation
*/
private computeReferencePoint(): Map<string, number> {
const reference = new Map<string, number>();
this.config.objectives.forEach(obj => {
const values = this.frontier.map(point => point.objectives.get(obj.name) || 0)
.filter(v => !isNaN(v));
if (values.length > 0) {
// Set reference point slightly worse than worst point in frontier
const worstValue = obj.direction === 'maximize' ? Math.min(...values) : Math.max(...values);
const offset = Math.abs(worstValue) * 0.1 + 0.01;
reference.set(obj.name, obj.direction === 'maximize' ? worstValue - offset : worstValue + offset);
} else {
reference.set(obj.name, obj.direction === 'maximize' ? 0 : 1);
}
});
return reference;
}
/**
* Enforce maximum frontier size by removing least diverse points
*/
private async enforceMaxSize(): Promise<void> {
if (!this.config.maxSize || this.frontier.length <= this.config.maxSize) {
return;
}
const optimized = await this.optimizeArchive(this.config.maxSize);
// Archive removed points if enabled
if (this.config.archiveEnabled) {
const removed = this.frontier.filter(point =>
!optimized.some(opt => opt.candidate.id === point.candidate.id)
);
this.archive.push(...removed);
}
this.frontier = optimized;
}
/**
* Compute diversity metric (OPTIMIZED with sampling)
*/
private computeDiversity(): number {
if (this.frontier.length < 2) return 0;
// OPTIMIZATION: Use sampling for large frontiers to avoid O(nĀ²) computation
if (this.frontier.length > 50) {
return this.computeDiversitySampled();
}
let totalDistance = 0;
let count = 0;
for (let i = 0; i < this.frontier.length; i++) {
const pointI = this.frontier[i];
if (!pointI) continue;
for (let j = i + 1; j < this.frontier.length; j++) {
const pointJ = this.frontier[j];
if (!pointJ) continue;
totalDistance += this.computeDistance(pointI, pointJ);
count++;
}
}
return count > 0 ? totalDistance / count : 0;
}
/**
* Compute spacing metric
*/
private computeSpacing(): number {
if (this.frontier.length < 2) return 0;
const distances: number[] = [];
for (let i = 0; i < this.frontier.length; i++) {
let minDist = Infinity;
for (let j = 0; j < this.frontier.length; j++) {
if (i !== j) {
const pointI = this.frontier[i];
const pointJ = this.frontier[j];
if (!pointI || !pointJ) continue;
const dist = this.computeDistance(pointI, pointJ);
minDist = Math.min(minDist, dist);
}
}
if (minDist !== Infinity) {
distances.push(minDist);
}
}
if (distances.length === 0) return 0;
const mean = distances.reduce((a, b) => a + b, 0) / distances.length;
const variance = distances.reduce((a, b) => a + Math.pow(b - mean, 2), 0) / distances.length;
return Math.sqrt(variance);
}
/**
* Compute spread metric
*/
private computeSpread(): number {
if (this.frontier.length < 2) return 0;
let maxSpread = 0;
for (const obj of this.config.objectives) {
const values = this.frontier.map(point => point.objectives.get(obj.name) || 0)
.filter(v => !isNaN(v));
if (values.length > 1) {
const range = Math.max(...values) - Math.min(...values);
maxSpread = Math.max(maxSpread, range);
}
}
return maxSpread;
}
/**
* Compute generational distance metric
*/
private computeGenerationalDistance(): number {
// Simplified implementation - in practice would compare against true Pareto front
return Math.random() * 0.1; // Placeholder
}
/**
* Compute distance between two Pareto points
*/
private computeDistance(a: ParetoPoint, b: ParetoPoint): number {
let sumSquares = 0;
for (const obj of this.config.objectives) {
const aValue = a.objectives.get(obj.name) || 0;
const bValue = b.objectives.get(obj.name) || 0;
if (!isNaN(aValue) && !isNaN(bValue)) {
sumSquares += Math.pow(aValue - bValue, 2);
}
}
return Math.sqrt(sumSquares);
}
/**
* Get cached objectives for a candidate
*/
private getCachedObjectives(candidate: PromptCandidate): Map<string, number> {
let objectives = this.objectiveCache.get(candidate.id);
if (!objectives) {
objectives = new Map();
this.config.objectives.forEach(obj => {
try {
const value = obj.extractor(candidate);
objectives!.set(obj.name, isNaN(value) ? 0 : value);
} catch {
objectives!.set(obj.name, 0);
}
});
this.objectiveCache.set(candidate.id, objectives);
}
return objectives;
}
/**
* Check if two objective maps are identical
*/
private areObjectivesIdentical(a: Map<string, number>, b: Map<string, number>): boolean {
if (a.size !== b.size) return false;
for (const [key, value] of a) {
const bValue = b.get(key);
if (bValue === undefined || value !== bValue) {
return false;
}
}
return true;
}
/**
* Check if convergence metrics should be updated
*/
private shouldUpdateConvergenceMetrics(): boolean {
return Date.now() - this.lastUpdateTimestamp > 10000; // Update every 10 seconds
}
/**
* Get cache key for hypervolume calculation
*/
private getHypervolumeCacheKey(reference?: Map<string, number>): string {
const frontierHash = this.getFrontierHash();
const refHash = reference ? this.hashMap(reference) : 'default';
return `${frontierHash}-${refHash}`;
}
/**
* Compute hypervolume with optimization
*/
private computeHypervolumeOptimized(referencePoint: Map<string, number>): number {
if (this.frontier.length === 0) return 0;
// Simplified hypervolume calculation for 2D case
if (this.config.objectives.length === 2) {
return this.computeHypervolume2D(referencePoint);
}
// For higher dimensions, use Monte Carlo approximation
return this.computeHypervolumeMonteCarloApproximation(referencePoint);
}
/**
* 2D hypervolume calculation
*/
private computeHypervolume2D(referencePoint: Map<string, number>): number {
if (this.frontier.length === 0) return 0;
const objectives = this.config.objectives;
if (objectives.length !== 2 || !objectives[0] || !objectives[1]) return 0;
const obj1 = objectives[0];
const obj2 = objectives[1];
const points = this.frontier.map(point => ({
x: point.objectives.get(obj1.name) || 0,
y: point.objectives.get(obj2.name) || 0
}));
const refX = referencePoint.get(obj1.name) || 0;
const refY = referencePoint.get(obj2.name) || 0;
// Sort points for hypervolume calculation
points.sort((a, b) => a.x - b.x);
let hypervolume = 0;
let prevX = refX;
for (let i = 0; i < points.length; i++) {
const point = points[i];
if (!point) continue;
if (point.x > prevX) {
hypervolume += (point.x - prevX) * (point.y - refY);
prevX = point.x;
}
}
return Math.max(0, hypervolume);
}
/**
* Monte Carlo approximation for higher-dimensional hypervolume
*/
private computeHypervolumeMonteCarloApproximation(referencePoint: Map<string, number>): number {
const sampleCount = 1000;
let dominatedCount = 0;
for (let i = 0; i < sampleCount; i++) {
const randomPoint = this.generateRandomPoint(referencePoint);
// Check if random point is dominated by any frontier point
for (const frontierPoint of this.frontier) {
if (this.isDominatedBy(randomPoint, frontierPoint)) {
dominatedCount++;
break;
}
}
}
const volume = this.calculateTotalVolume(referencePoint);
return (dominatedCount / sampleCount) * volume;
}
/**
* Generate random point within the reference space
*/
private generateRandomPoint(referencePoint: Map<string, number>): Map<string, number> {
const point = new Map<string, number>();
for (const obj of this.config.objectives) {
const refValue = referencePoint.get(obj.name) || 0;
// Generate random value between reference and best possible value
const maxValue = Math.max(...this.frontier.map(p => p.objectives.get(obj.name) || 0));
const randomValue = refValue + Math.random() * (maxValue - refValue);
point.set(obj.name, randomValue);
}
return point;
}
/**
* Check if point A is dominated by frontier point B
*/
private isDominatedBy(pointA: Map<string, number>, frontierPoint: ParetoPoint): boolean {
let betterInAny = false;
for (const obj of this.config.objectives) {
const aValue = pointA.get(obj.name) || 0;
const bValue = frontierPoint.objectives.get(obj.name) || 0;
if (obj.direction === 'maximize') {
if (bValue < aValue) return false;
if (bValue > aValue) betterInAny = true;
} else {
if (bValue > aValue) return false;
if (bValue < aValue) betterInAny = true;
}
}
return betterInAny;
}
/**
* Calculate total volume of reference space
*/
private calculateTotalVolume(referencePoint: Map<string, number>): number {
let volume = 1;
for (const obj of this.config.objectives) {
const refValue = referencePoint.get(obj.name) || 0;
const maxValue = Math.max(...this.frontier.map(p => p.objectives.get(obj.name) || 0));
volume *= Math.abs(maxValue - refValue);
}
return volume;
}
/**
* Compute diversity with sampling for large frontiers
*/
private computeDiversitySampled(): number {
const sampleSize = Math.min(50, this.frontier.length);
const sampledIndices = new Set<number>();
// Random sampling
while (sampledIndices.size < sampleSize) {
sampledIndices.add(Math.floor(Math.random() * this.frontier.length));
}
const sampledPoints = Array.from(sampledIndices)
.map(i => this.frontier[i])
.filter(point => point !== undefined);
let totalDistance = 0;
let count = 0;
for (let i = 0; i < sampledPoints.length; i++) {
const pointI = sampledPoints[i];
if (!pointI) continue;
for (let j = i + 1; j < sampledPoints.length; j++) {
const pointJ = sampledPoints[j];
if (!pointJ) continue;
totalDistance += this.computeDistance(pointI, pointJ);
count++;
}
}
return count > 0 ? totalDistance / count : 0;
}
/**
* Get hash of frontier for cache keys
*/
private getFrontierHash(): string {
const sortedIds = this.frontier
.map(p => p.candidate.id)
.sort()
.join(',');
return this.hashString(sortedIds);
}
/**
* Hash a map for cache keys
*/
private hashMap(map: Map<string, number>): string {
const entries = Array.from(map.entries())
.sort(([a], [b]) => a.localeCompare(b))
.map(([k, v]) => `${k}:${v}`)
.join(',');
return this.hashString(entries);
}
/**
* Simple hash function for strings
*/
private hashString(str: string): string {
let hash = 0;
for (let i = 0; i < str.length; i++) {
const char = str.charCodeAt(i);
hash = ((hash << 5) - hash) + char;
hash = hash & hash; // Convert to 32bit integer
}
return hash.toString(36);
}
/**
* Setup memory leak detection integration
*/
private setupMemoryLeakDetection(): void {
// Initialize memory leak detection if not already done
MemoryLeakIntegration.initialize();
}
/**
* Estimate memory size of a candidate for leak detection
*/
private estimateCandidateSize(candidate: PromptCandidate): number {
try {
// Rough estimation based on JSON serialization
const serialized = JSON.stringify(candidate);
return serialized.length * 2; // Assuming UTF-16 encoding
} catch {
// Fallback estimation
return 1024; // 1KB default
}
}
/**
* Perform memory cleanup and optimization
*/
async performMemoryCleanup(): Promise<{ freedMemory: number; cleanedObjects: number }> {
let freedMemory = 0;
let cleanedObjects = 0;
// Clean objective cache
const oldCacheSize = this.objectiveCache.size;
this.objectiveCache.clear();
cleanedObjects += oldCacheSize;
// Clean hypervolume cache
const oldHypervolumeSize = this.hypervolumeCache.size;
this.hypervolumeCache.clear();
cleanedObjects += oldHypervolumeSize;
// Clean old convergence history (keep only last 10 entries)
if (this.convergenceHistory.length > 10) {
const removed = this.convergenceHistory.splice(0, this.convergenceHistory.length - 10);
cleanedObjects += removed.length;
freedMemory += removed.length * 200; // Rough estimate
}
// Clean archive if it's too large
if (this.archive.length > 1000) {
const removed = this.archive.splice(0, this.archive.length - 1000);
for (const point of removed) {
const candidateSize = this.estimateCandidateSize(point.candidate);
freedMemory += candidateSize;
MemoryLeakIntegration.trackParetoOperation('remove', point.candidate.id, candidateSize);
}
cleanedObjects += removed.length;
}
return { freedMemory, cleanedObjects };
}
}
/**
* Dominance Index for efficient dominance checking
*/
class DominanceIndex {
private points: ParetoPoint[] = [];
/**
* Check if a point is dominated by any indexed point
*/
isDominated(point: ParetoPoint): boolean {
return this.points.some(existing => this.dominates(existing, point));
}
/**
* Add a point to the index
*/
addPoint(point: ParetoPoint): void {
this.points.push(point);
}
/**
* Remove points from the index
*/
removePoints(points: ParetoPoint[]): void {
const idsToRemove = new Set(points.map(p => p.candidate.id));
this.points = this.points.filter(p => !idsToRemove.has(p.candidate.id));
}
/**
* Find points dominated by the given point
*/
findDominated(point: ParetoPoint): ParetoPoint[] {
return this.points.filter(existing => this.dominates(point, existing));
}
/**
* Check if point a dominates point b (simplified)
*/
private dominates(a: ParetoPoint, b: ParetoPoint): boolean {
// This is a simplified dominance check
// In practice, this would use the same logic as the main ParetoFrontier class
let betterInAny = false;
for (const [objName, aValue] of a.objectives) {
const bValue = b.objectives.get(objName) || 0;
// Assume maximization for simplicity
if (aValue < bValue) return false;
if (aValue > bValue) betterInAny = true;
}
return betterInAny;
}
}