GeneticAlgorithmMultiObjective

alirezamohamad414 · library · 422 行 · 点赞 5 · TradingView 原页

本页源码来自 TradingView 公开发布的开源脚本,版权归原作者所有, 请遵循其原始许可(Pine 脚本常见 CC BY-NC-SA / MPL-2.0 / MIT)。 本项目仅用于研究检索与许可范围内的移植。

Pine Script

//@version=6
//@description Fast multi-objective genetic algorithm (NSGA-II) for Pine Script. All objectives are MAXIMIZED. Real-coded genes with SBX crossover and polynomial mutation, true Pareto fronts, per-front crowding distance, and elitist environmental selection.
library("GeneticAlgorithmMultiObjective", overlay = false)
 
// ============================================
// ثوابت داخلی
// ============================================
const float CROWD_INF = 1.0e12
 
// ============================================
// انواع داده‌ها (Types)
// ============================================
 
// @type A candidate solution.
// @field genes Gene values.
// @field objectives Objective values (all maximized). Filled by the user.
// @field fitness Free slot for user data.
// @field rank Pareto front index (0 = best front).
// @field crowding Crowding distance inside its front (bigger = more isolated = better).
export type GA_Chromosome
    array<float> genes
    array<float> objectives
    float        fitness
    int          rank
    float        crowding
 
// @type Algorithm settings.
// @field populationSize Number of individuals.
// @field geneCount Number of genes per individual.
// @field objectiveCount Number of objectives.
// @field minValues Lower bound of each gene.
// @field maxValues Upper bound of each gene.
// @field mutationRate Per-gene mutation probability (a good default is 1 / geneCount).
// @field crossoverRate Probability that two parents are recombined.
// @field elitismRate Share of the population kept as elites in createNextGeneration.
// @field tournamentSize Tournament size (2 = binary tournament).
// @field maxGenerations Free slot for the caller's loop.
// @field etaCrossover SBX distribution index (10 to 20; larger = children closer to parents).
// @field etaMutation Polynomial mutation distribution index (15 to 30).
// @field useSBX true = SBX + polynomial mutation, false = uniform crossover + random reset.
export type GA_Config
    int          populationSize
    int          geneCount
    int          objectiveCount
    array<float> minValues
    array<float> maxValues
    float        mutationRate
    float        crossoverRate
    float        elitismRate
    int          tournamentSize
    int          maxGenerations
    float        etaCrossover
    float        etaMutation
    bool         useSBX
 
// ============================================
// توابع کمکی
// ============================================
 
// @function Creates a GA_Config.
// @returns GA_Config
export createConfig(int populationSize, int geneCount, int objectiveCount, array<float> minValues, array<float> maxValues, float mutationRate, float crossoverRate, float elitismRate, int tournamentSize, int maxGenerations, float etaCrossover, float etaMutation, bool useSBX) =>
    GA_Config.new(populationSize, geneCount, objectiveCount, minValues, maxValues, mutationRate, crossoverRate, elitismRate, tournamentSize, maxGenerations, etaCrossover, etaMutation, useSBX)
 
// @function Random float in [minVal, maxVal).
export randomFloat(float minVal, float maxVal) =>
    math.random(minVal, maxVal)
 
// @function Random integer in [minVal, maxVal) (upper bound excluded).
export randomInt(int minVal, int maxVal) =>
    int r = int(math.floor(math.random(minVal, maxVal)))
    math.min(maxVal - 1, math.max(minVal, r))
 
// ============================================
// ایجاد کروموزوم و جمعیت اولیه
// ============================================
 
// @function Creates one random chromosome inside the gene bounds.
export createRandomChromosome(GA_Config config) =>
    int gCount = config.geneCount
    array<float> minArr = config.minValues
    array<float> maxArr = config.maxValues
    genes = array.new<float>()
    for i = 0 to gCount - 1
        genes.push(math.random(minArr.get(i), maxArr.get(i)))
    GA_Chromosome.new(genes, array.new<float>(config.objectiveCount, 0.0), 0.0, 999, 0.0)
 
// @function Creates the initial random population.
export initializePopulation(GA_Config config) =>
    int pSize = config.populationSize
    population = array.new<GA_Chromosome>()
    for i = 0 to pSize - 1
        population.push(createRandomChromosome(config))
    population
 
// @function Deep copy of a chromosome.
export cloneChromosome(GA_Chromosome chrom) =>
    GA_Chromosome.new(array.copy(chrom.genes), array.copy(chrom.objectives), chrom.fitness, chrom.rank, chrom.crowding)
 
// ============================================
// توابع داخلی NSGA-II (روی آرایه تخت، بدون دسترسی به فیلدها)
// ============================================
 
// true if individual a dominates b (maximization). objectives are stored flat: flat[i*m + k]
flatDominates(array<float> flat, int a, int b, int m) =>
    bool better = false
    bool ok = true
    int oa = a * m
    int ob = b * m
    int k = 0
    while k < m
        float va = flat.get(oa + k)
        float vb = flat.get(ob + k)
        if va < vb
            ok := false
            break
        if va > vb
            better := true
        k += 1
    ok and better
 
// @function Dominance test between two chromosomes (all objectives maximized).
export dominates(GA_Chromosome a, GA_Chromosome b) =>
    bool ok = true
    bool better = false
    int m = a.objectives.size()
    int k = 0
    while k < m
        float va = a.objectives.get(k)
        float vb = b.objectives.get(k)
        if va < vb
            ok := false
            break
        if va > vb
            better := true
        k += 1
    ok and better
 
// @function Fast non-dominated sorting (true Pareto fronts) plus crowding distance per front, in one pass. Sets rank and crowding on every chromosome. Call this before selection.
// @param population The evaluated population (objectives filled).
// @param objectiveCount Number of objectives.
// @returns The same array.
export rankPopulation(array<GA_Chromosome> population, int objectiveCount) =>
    int n = population.size()
    int m = objectiveCount
    if n > 0
        // --- استخراج اهداف در یک آرایه تخت ---
        flat = array.new<float>(n * m, 0.0)
        for i = 0 to n - 1
            objs = population.get(i).objectives
            for k = 0 to m - 1
                flat.set(i * m + k, objs.get(k))
 
        // --- شمارش تعداد غالب‌کننده‌ها (هر جفت فقط یک بار) ---
        cnt = array.new<int>(n, 0)
        if n > 1
            for i = 0 to n - 2
                for j = i + 1 to n - 1
                    bool iBetter = false
                    bool jBetter = false
                    int oi = i * m
                    int oj = j * m
                    for k = 0 to m - 1
                        float vi = flat.get(oi + k)
                        float vj = flat.get(oj + k)
                        if vi > vj
                            iBetter := true
                        else if vi < vj
                            jBetter := true
                        if iBetter and jBetter
                            break
                    if iBetter and not jBetter
                        cnt.set(j, cnt.get(j) + 1)
                    else if jBetter and not iBetter
                        cnt.set(i, cnt.get(i) + 1)
 
        // --- جدا کردن جبهه‌ها ---
        ranks = array.new<int>(n, -1)
        array<int> front = array.new<int>()
        for i = 0 to n - 1
            if cnt.get(i) == 0
                ranks.set(i, 0)
                front.push(i)
        int f = 0
        while front.size() > 0
            array<int> nxt = array.new<int>()
            for p in front
                for q = 0 to n - 1
                    if ranks.get(q) < 0 and flatDominates(flat, p, q, m)
                        int c = cnt.get(q) - 1
                        cnt.set(q, c)
                        if c == 0
                            ranks.set(q, f + 1)
                            nxt.push(q)
            front := nxt
            f += 1
        int nf = f
 
        // --- فاصله ازدحام برای هر جبهه (مرتب‌سازی بومی) ---
        crowd = array.new<float>(n, 0.0)
        vals  = array.new<float>(n, 0.0)
        fMin  = array.new<float>(nf, 0.0)
        fMax  = array.new<float>(nf, 0.0)
        prev1 = array.new<int>(nf, -1)
        prev2 = array.new<int>(nf, -1)
        for k = 0 to m - 1
            for i = 0 to n - 1
                vals.set(i, flat.get(i * m + k))
            idx = array.sort_indices(vals, order.ascending)
 
            // گذر اول: min و max هر جبهه
            prev1.fill(-1)
            for t = 0 to n - 1
                int ix = idx.get(t)
                int r = ranks.get(ix)
                float v = vals.get(ix)
                if prev1.get(r) < 0
                    fMin.set(r, v)
                    prev1.set(r, ix)
                fMax.set(r, v)
 
            // گذر دوم: محاسبه فاصله همسایه‌ها داخل هر جبهه
            prev1.fill(-1)
            prev2.fill(-1)
            for t = 0 to n - 1
                int ix = idx.get(t)
                int r = ranks.get(ix)
                int p1 = prev1.get(r)
                int p2 = prev2.get(r)
                if p1 >= 0
                    if p2 < 0
                        crowd.set(p1, CROWD_INF)
                    else
                        float rng = fMax.get(r) - fMin.get(r)
                        if rng > 1.0e-12 and crowd.get(p1) < CROWD_INF
                            crowd.set(p1, crowd.get(p1) + (vals.get(ix) - vals.get(p2)) / rng)
                prev2.set(r, p1)
                prev1.set(r, ix)
            for r = 0 to nf - 1
                int last = prev1.get(r)
                if last >= 0
                    crowd.set(last, CROWD_INF)
 
        // --- نوشتن نتایج ---
        for i = 0 to n - 1
            ch = population.get(i)
            ch.rank := ranks.get(i)
            ch.crowding := crowd.get(i)
    population
 
// ============================================
// انتخاب
// ============================================
 
// @function Tournament selection by rank, then crowding. Population must be ranked.
export tournamentSelection(array<GA_Chromosome> population, int tournamentSize) =>
    int n = population.size()
    GA_Chromosome best = population.get(math.min(n - 1, int(math.random(0, n))))
    int t = 1
    while t < tournamentSize
        GA_Chromosome cand = population.get(math.min(n - 1, int(math.random(0, n))))
        if cand.rank < best.rank or (cand.rank == best.rank and cand.crowding > best.crowding)
            best := cand
        t += 1
    best
 
// @function Picks the best targetSize individuals by (rank, crowding). Population must be ranked. Returns references (no copies).
export selectBest(array<GA_Chromosome> population, int targetSize) =>
    int n = population.size()
    array<GA_Chromosome> result = array.new<GA_Chromosome>()
    if targetSize > 0
        if n <= targetSize
            result := array.copy(population)
        else
            rk = array.new<float>(n, 0.0)
            for i = 0 to n - 1
                rk.set(i, population.get(i).rank)
            idx = array.sort_indices(rk, order.ascending)
            int t = 0
            while t < n and result.size() < targetSize
                int r = population.get(idx.get(t)).rank
                int e = t
                while e < n and population.get(idx.get(e)).rank == r
                    e += 1
                int groupSize = e - t
                int remaining = targetSize - result.size()
                if groupSize <= remaining
                    for k = t to e - 1
                        result.push(population.get(idx.get(k)))
                else
                    cr = array.new<float>(groupSize, 0.0)
                    for k = 0 to groupSize - 1
                        cr.set(k, population.get(idx.get(t + k)).crowding)
                    co = array.sort_indices(cr, order.descending)
                    for k = 0 to remaining - 1
                        result.push(population.get(idx.get(t + co.get(k))))
                t := e
    result
 
// @function Returns the first Pareto front (rank 0). Population must be ranked.
export getParetoFront(array<GA_Chromosome> population) =>
    front = array.new<GA_Chromosome>()
    for ch in population
        if ch.rank == 0
            front.push(ch)
    front
 
// ============================================
// عملگرهای ژنتیکی
// ============================================
 
sbxGene(float p1, float p2, float lo, float hi, float eta) =>
    float res = p1
    if math.abs(p1 - p2) > 1.0e-12
        float u = math.random()
        float ex = 1.0 / (eta + 1.0)
        float beta = u <= 0.5 ? math.pow(2.0 * u, ex) : math.pow(1.0 / (2.0 * (1.0 - u)), ex)
        float c = math.random() < 0.5 ? 0.5 * ((1.0 + beta) * p1 + (1.0 - beta) * p2) : 0.5 * ((1.0 - beta) * p1 + (1.0 + beta) * p2)
        res := math.max(lo, math.min(hi, c))
    res
 
// @function Uniform crossover. Returns a new child.
export crossoverUniform(GA_Chromosome parent1, GA_Chromosome parent2, GA_Config config) =>
    int gCount = config.geneCount
    array<float> p1g = parent1.genes
    array<float> p2g = parent2.genes
    childGenes = array.new<float>()
    for i = 0 to gCount - 1
        childGenes.push(math.random() < 0.5 ? p1g.get(i) : p2g.get(i))
    GA_Chromosome.new(childGenes, array.new<float>(config.objectiveCount, 0.0), 0.0, 999, 0.0)
 
// @function Simulated Binary Crossover (SBX), bounded. Returns a new child.
export crossoverSBX(GA_Chromosome parent1, GA_Chromosome parent2, GA_Config config) =>
    int gCount = config.geneCount
    float eta = config.etaCrossover
    array<float> p1g = parent1.genes
    array<float> p2g = parent2.genes
    array<float> minArr = config.minValues
    array<float> maxArr = config.maxValues
    childGenes = array.new<float>()
    for i = 0 to gCount - 1
        float g = p1g.get(i)
        if math.random() < 0.5
            g := sbxGene(g, p2g.get(i), minArr.get(i), maxArr.get(i), eta)
        childGenes.push(g)
    GA_Chromosome.new(childGenes, array.new<float>(config.objectiveCount, 0.0), 0.0, 999, 0.0)
 
// @function Random-reset mutation (in place).
export mutateUniform(GA_Chromosome chrom, GA_Config config) =>
    float rate = config.mutationRate
    array<float> minArr = config.minValues
    array<float> maxArr = config.maxValues
    array<float> genes = chrom.genes
    int gCount = config.geneCount
    for i = 0 to gCount - 1
        if math.random() < rate
            genes.set(i, math.random(minArr.get(i), maxArr.get(i)))
    chrom
 
// @function Polynomial mutation (in place). Small local changes, much more accurate than random reset.
export mutatePolynomial(GA_Chromosome chrom, GA_Config config) =>
    float rate = config.mutationRate
    float ex = 1.0 / (config.etaMutation + 1.0)
    array<float> minArr = config.minValues
    array<float> maxArr = config.maxValues
    array<float> genes = chrom.genes
    int gCount = config.geneCount
    for i = 0 to gCount - 1
        if math.random() < rate
            float lo = minArr.get(i)
            float hi = maxArr.get(i)
            float u = math.random()
            float delta = u < 0.5 ? math.pow(2.0 * u, ex) - 1.0 : 1.0 - math.pow(2.0 * (1.0 - u), ex)
            genes.set(i, math.max(lo, math.min(hi, genes.get(i) + delta * (hi - lo))))
    chrom
 
// @function Mutation chosen by config.useSBX.
export mutate(GA_Chromosome chrom, GA_Config config) =>
    if config.useSBX
        mutatePolynomial(chrom, config)
    else
        mutateUniform(chrom, config)
    chrom
 
// ============================================
// تولید نسل
// ============================================
 
// @function Creates `count` unevaluated children from a ranked population (call rankPopulation first, or use the output of environmentalSelection).
export createOffspring(array<GA_Chromosome> population, GA_Config config, int count) =>
    offspring = array.new<GA_Chromosome>()
    float cr = config.crossoverRate
    int ts = config.tournamentSize
    while offspring.size() < count
        GA_Chromosome parent1 = tournamentSelection(population, ts)
        GA_Chromosome child = na
        if math.random() < cr
            GA_Chromosome parent2 = tournamentSelection(population, ts)
            child := config.useSBX ? crossoverSBX(parent1, parent2, config) : crossoverUniform(parent1, parent2, config)
        else
            child := cloneChromosome(parent1)
            child.objectives := array.new<float>(config.objectiveCount, 0.0)
            child.rank := 999
            child.crowding := 0.0
        mutate(child, config)
        offspring.push(child)
    offspring
 
// @function True NSGA-II survivor selection. Pass parents + evaluated offspring merged in one array; returns the best populationSize individuals (ranked, with crowding set).
export environmentalSelection(array<GA_Chromosome> combined, GA_Config config) =>
    rankPopulation(combined, config.objectiveCount)
    selectBest(combined, config.populationSize)
 
// @function Simple generational step with elitism (compatible with the old API). The returned population has elites evaluated and new children with zero objectives (evaluate them before the next call).
export createNextGeneration(array<GA_Chromosome> population, GA_Config config) =>
    int popSize = config.populationSize
    rankPopulation(population, config.objectiveCount)
    int eliteCount = math.min(popSize, math.max(1, int(math.floor(popSize * config.elitismRate))))
    newPop = selectBest(population, eliteCount)
    offspring = createOffspring(population, config, popSize - newPop.size())
    array.concat(newPop, offspring)
    newPop

← 返回列表