Java Perlin Noise height map generation lacks desired randomness

I am trying to generate a height map using Perlin Noise, but am having trouble with generating truly unique maps. That is, each one is a minor variation of all the others. Two examples are below:

And here is my code (most was just copied and pasted from Ken Perlin's implementation, though adapted for 2D):

public class HeightMap {

    private ArrayList<Point> map = new ArrayList<>();
    private double elevationMax, elevationMin;

    private final int[] P = new int[512], PERMUTATION = { 151,160,137,91,90,15,
            131,13,201,95,96,53,194,233,7,225,140,36,103,30,69,142,8,99,37,240,21,10,23,
            190, 6,148,247,120,234,75,0,26,197,62,94,252,219,203,117,35,11,32,57,177,33,
            88,237,149,56,87,174,20,125,136,171,168, 68,175,74,165,71,134,139,48,27,166,
            77,146,158,231,83,111,229,122,60,211,133,230,220,105,92,41,55,46,245,40,244,
            102,143,54, 65,25,63,161, 1,216,80,73,209,76,132,187,208, 89,18,169,200,196,
            135,130,116,188,159,86,164,100,109,198,173,186, 3,64,52,217,226,250,124,123,
            5,202,38,147,118,126,255,82,85,212,207,206,59,227,47,16,58,17,182,189,28,42,
            223,183,170,213,119,248,152, 2,44,154,163, 70,221,153,101,155,167, 43,172,9,
            129,22,39,253, 19,98,108,110,79,113,224,232,178,185, 112,104,218,246,97,228,
            251,34,242,193,238,210,144,12,191,179,162,241, 81,51,145,235,249,14,239,107,
            49,192,214, 31,181,199,106,157,184, 84,204,176,115,121,50,45,127, 4,150,254,
            138,236,205,93,222,114,67,29,24,72,243,141,128,195,78,66,215,61,156,180
    };

    public HeightMap() {
        this.map = null;
        this.elevationMax = 0.0;
        this.elevationMin = 0.0;
    }

    public HeightMap(HeightMap map) {
        this.map = map.getPoints();
        this.elevationMax = map.getElevationMax();
        this.elevationMin = map.getElevationMin();
    }

    /**
     * Generates a Height Map that is, along an imaginary z-axis, centered around the median elevation, given the following parameters:
     * @param mapWidth the width [x] of the map
     * @param mapHeight the height [y] of the map
     * @param tileWidth the width [x] of each tile, or Point
     * @param tileHeight the height [y] of each tile, or Point
     * @param elevationMax the maximum elevation [z] of the map
     * @param elevationMin the minimum elevation [z] of the map
     */
    public HeightMap(int mapWidth, int mapHeight, int tileWidth, int tileHeight, double elevationMax, double elevationMin) {
        this.elevationMax = elevationMax;
        this.elevationMin = elevationMin;

        for (int i=0; i < 256 ; i++) {
            P[256+i] = P[i] = PERMUTATION[i];
        }

        int numTilesX = mapWidth / tileWidth;
        int numTilesY = mapHeight / tileHeight;

        Random r = new Random();

        for (int t = 0; t < numTilesX * numTilesY; t++) {
            double x = t % numTilesX;
            double y = (t - x) / numTilesX;
            r = new Random();
            x += r.nextDouble();
            y += r.nextDouble();

            this.map.add(new Point(x, y, lerp(noise(x, y, 13), (elevationMin + elevationMax) / 2, elevationMax), tileWidth, tileHeight));
        }
    }

    /**
     * Ken Perlin's Improved Noise Java Implementation (https://mrl.cs.nyu.edu/~perlin/noise/)
     * Adapted for 2D
     * @param x the x-coordinate on the map
     * @param y the y-coordinate on the map
     * @param stretch the factor by which adjacent points are smoothed
     * @return a value between -1.0 and 1.0 to represent the height of the terrain at (x, y)
     */
    private double noise(double x, double y, double stretch) {
        x /= stretch;
        y /= stretch;
        int X = (int)Math.floor(x) & 255, Y = (int)Math.floor(y) & 255;

        x -= Math.floor(x);
        y -= Math.floor(y);

        double u = fade(x),
               v = fade(y);

        int AA = P[P[X    ] + Y    ],
            AB = P[P[X    ] + Y + 1],
            BA = P[P[X + 1] + Y    ],
            BB = P[P[X + 1] + Y + 1];

        return lerp(v, lerp(u, grad(P[AA], x, y), grad(P[BA], x - 1, y)), lerp(u, grad(P[AB], x, y - 1), grad(P[BB], x - 1, y - 1)));
    }

    private double fade(double t) {
        return t * t * t * (t * (t * 6 - 15) + 10);
    }

    private double lerp(double t, double a, double b) {
        return a + t * (b - a);
    }

    //Riven's Optimization (http://riven8192.blogspot.com/2010/08/calculate-perlinnoise-twice-as-fast.html)
    private double grad(int hash, double x, double y) {
        switch(hash & 0xF)
        {
            case 0x0:
            case 0x8:
                return  x + y;
            case 0x1:
            case 0x9:
                return -x + y;
            case 0x2:
            case 0xA:
                return  x - y;
            case 0x3:
            case 0xB:
                return -x - y;
            case 0x4:
            case 0xC:
                return  y + x;
            case 0x5:
            case 0xD:
                return -y + x;
            case 0x6:
            case 0xE:
                return  y - x;
            case 0x7:
            case 0xF:
                return -y - x;
            default: return 0; // never happens
        }
    }
}

Is this problem inherent in Perlin Noise because the 'height' is calculated from nearly the same (x, y) coordinate each time? Is there a way to implement the noise function so that it doesn't depend on the (x, y) coordinate of each point but still looks like terrain? Any help is greatly appreciated.

With some help from a friend of mine, I resolved the problem. Because I was using the same PERMUTATION array each generation cycle, the noise calculation was using the same base values each time. To fix this, I made a method permute() that filled PERMUTATION with the numbers 0 to 255 in a random, non-repeating order. I changed the instantiation of PERMUTATION to just be a new int[].

private final int[] P = new int[512], PERMUTATION = new int[256];

...

public void permute() {
        for (int i = 0; i < PERMUTATION.length; i++) {
            PERMUTATION[i] = i;
        }

        Random r = new Random();
        int rIndex, rIndexVal;
        for (int i = 0; i < PERMUTATION.length; i++) {
            rIndex = r.nextInt(PERMUTATION.length);
            rIndexVal = PERMUTATION[rIndex];
            PERMUTATION[rIndex] = PERMUTATION[i];
            PERMUTATION[i] = rIndexVal;
        }
    }